問題文

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

入力例 1Copy

7 3
2 4 7
1 3
2 1 7

出力例 1Copy

3
3

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

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

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

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

入力例 2Copy

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

出力例 2Copy

8
0
1
0
1
0
0