Problem Description

$ N $ stones are arranged in a row from left to right. Initially, there are no obstacles on any of the stones, so you can freely step on them.

Process $ Q $ queries. There are two types of queries, and their input format and content are as follows:

• 1 p: If there is no obstacle on the $ p_i $th stone from the left, place an obstacle; if there is one, remove it. You cannot step on a stone with an obstacle.
• 2 l r: Starting from the $ l $th stone from the left, repeatedly perform the operations "jump one stone to the right" or "jump two stones to the right" to reach the $ r $th stone from the left without stepping on any stone with an obstacle. Output the total number of ways to do this, modulo $ 10^9+7 $. If there is an obstacle on the $ l $th or $ r $th stone, output $ 0 $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

For each query with the input format 2 l r, output the answer in the order the queries are given, each on a new line.

Sample Input and Output

Sample Input #1

7 3
2 4 7
1 3
2 1 7

Sample Output #1

3
3

Sample Input #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

Sample Output #2

8
0
1
0
1
0
0

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 10^9$
• $1\ \leq\ Q\ \leq\ 10^5$
• $1\ \leq\ p\ \leq\ N$
• $1\ \leq\ l\ <\ r\ \leq\ N$
• All inputs are integers

Sample Explanation 1

In the first query, the following ways of moving are possible:
- Jump one stone to the right, jump one stone to the right, jump one stone to the right.
- Jump one stone to the right, jump two stones to the right.
- Jump two stones to the right, jump one stone to the right.

In the third query, the following ways of moving are possible:
- Jump one stone to the right, jump two stones to the right, jump one stone to the right, jump one stone to the right, jump one stone to the right.
- Jump one stone to the right, jump two stones to the right, jump one stone to the right, jump two stones to the right.
- Jump one stone to the right, jump two stones to the right, jump two stones to the right, jump one stone to the right.

见题面 Input 部分

见题面 Output 部分