Anil is the best coder in his class. He is in love with his classmate Gowthami. One day he proposes her. She wants him to prove that his love is actually true. So, she poses the following problem:

There is an array of size n. Initially all the elements are zero. Now there will be two types of operations:

• Update the array.
• Query the array.

In case of update, you will be given a range [l, r]. To the kth element in this range (l and r inclusive), you need to add kth Fibonacci number.

In case of query, you will be given a range [l, r], for which you need to find the sum of all elements in the range (including l and r).

Anil hopes you can help him in this regard.

Input

The first line contains n (1 <= n <= 10⁶) and q (1 <= q <= 5*10⁴), the number of operations to be performed. The next q lines contain 3 space separated integers. If the first integer is 0, then it's an update operation. If it is 1, then it's a query operation. The next two integers specify l and r. (1 <= l <= r <= n)

Output

For each query print one integer per line specifying the sum in the corresponding range. Since the sum can be very large, output Answer modulo 10⁹ + 7.

Example

Input:
5 6
0 1 5
0 2 4
0 1 3
1 2 4
1 1 5
1 4 5

Output:
13
20
10

Explanation

After the first update the array looks as follows: 1 1 2 3 5

After 2nd update: 1 2 3 5 5

After 3rd update: 2 3 5 5 5

Hence from the above array, we have the outputs for the queries.

Note: Fibonacci Series starts as 1, 1, 2, 3, ...