配点 : 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