D - Dangerous Hopscotch /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 900

問題文

N 個の石が左から右に一列に並んでいます。最初、それぞれの石の上には何も障害物が置かれていないので、自由に乗ることができます。

Q 個のクエリを処理してください。クエリには 2 種類あり、入力形式とクエリの内容は以下のとおりです。

  • 1 p: 左から p_i 番目の石の上に障害物が置かれていなければ障害物を置き、置かれていれば障害物を取り除く。障害物が置かれた石の上には、乗ることができない。
  • 2 l r: 左から l 番目の石の上からスタートし、「1 つ右の石にジャンプする」「2 つ右の石にジャンプする」という操作を繰り返して、障害物が置かれた石の上に一度も乗らずに左から r 番目の石の上にたどり着く方法の総数を 10^9+7 で割った余りを求め、出力する。ただし、左から l 番目や r 番目の石の上に障害物が置かれているときは、0 通りとする。

制約

  • 2 ≤ N ≤ 10^9
  • 1 ≤ Q ≤ 10^5
  • 1 ≤ p ≤ N
  • 1 ≤ l < r ≤ N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
Query_1
:
Query_Q

出力

2 l r という入力形式のクエリに対する答えを、クエリが与えられた順にそれぞれ 1 行ずつ出力せよ。


入力例 1

7 3
2 4 7
1 3
2 1 7

出力例 1

3
3

最初のクエリでは、次のような移動の仕方があります。

  • 1 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプする。
  • 1 つ右にジャンプし、2 つ右にジャンプする。
  • 2 つ右にジャンプし、1 つ右にジャンプする。

3 個目のクエリでは、次のような移動の仕方があります。

  • 1 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプする。
  • 1 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプし、2 つ右にジャンプする。
  • 1 つ右にジャンプし、2 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプする。

入力例 2

10 10
2 2 7
1 3
2 2 3
2 1 2
1 5
2 5 8
2 1 6
2 3 4
1 2
2 1 10

出力例 2

8
0
1
0
1
0
0