問題文

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
• 入力は全て整数

入力例 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