AT_yahoo_procon2019_final_d 危险的跳房子

题目描述

$N$块石头从左到右排成一列。最初，每一块石头上都没有放置任何障碍物，你可以随便坐。

总共有$Q$个查询。查询有$2$种类型，输入格式和查询内容如下：

• 1 p: 如果从左数第$p_i$块石头上没有障碍物，就放置障碍物，如果放置的话就去除障碍物。不能坐在放置障碍物的石头上。
• 2 l r: 从左数第$l$个石头上开始，反复进行“跳到右$1$个石头”、“跳到右$2$个的石头”的操作，求出一次也不坐在放置障碍物的石头上而从第$l$个石头到第$r$个石头上的方法总数除以$10^9+7$的余数，并输出。但是，在从左数第$l$个或第$r$个石头上有障碍物时，输出$0$条。

输入格式

输入以下形式

$N$ $Q$ $Query_1$ : $Query_Q$

输出格式

2 l r 根据输入形式的查询回答，按照查询顺序分别输出一行。

样例 #1

样例输入 #1

7 3
2 4 7
1 3
2 1 7

样例输出 #1

3
3

样例 #2

样例输入 #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

提示

规定条件

• $2\ <\ =\ N\ <\ =\ 10^9$
• $1\ <\ =\ Q\ <\ =\ 10^5$
• $1\ <\ =\ p\ <\ =\ N$
• $1\ <\ =\ l\ <\ r\ <\ =\ N$
• 输入全部为整数

示例说明1

在第一个查询中，有以下移动方法：向右一跳，向右一跳，向右一跳。向右一跳，向右两跳。向右两跳，向右一跳。在第三个查询中，有以下移动方法：向右一跳，向右两跳，向右一跳，向右一跳，向右一跳，向右一跳。向右一跳，向右两跳，向右一跳，向右两跳。向右一跳，向右两跳，向右两跳，向右一跳。