Problems involving queries and recurrences are very common in ICPC. In this problem, we are going to mix a little both topics. Given the recurrence $F_n = a \times F_{n-1} + b \times F_{n-2} + k$ and an array $A$ with $N$ values, write a program to perform $Q$ queries with the following format:

- 1 $a$ $b$ $k$: Increase each value in array $A$ whose position is within the range $[a,b]$ with the value $F_n$, where $n = a \times b$ ($1 \le a \le b \le N$, $1 \le k \le 2N$).
- 2 $a$ $b$: Return the sum of values $A_a + A_{a+1} + ... + A_b$. This value can be very big, so print the answer modulo $1000000007$. ($1 \le a \le b \le N$).

The input contains in the first line two integer numbers: $N$ ($1 \le N \le 10^5$) and $Q$ ($1 \le Q \le 10^5$). The following $Q$ lines contain the information of the queries, as it was explained above. The recurrence always has two base cases:

$F[0] = 0$ and $F[1] = k$. In addition, at the beginning each value of the array $A[i] = 0$.

For each query of kind 2, print the corresponding result.

Input

10 5
1 1 2 1
2 1 6
1 1 3 2
2 1 4
2 2 6

Output

4
40
26

Input

10 5
1 3 5 15
2 1 10
1 4 6 5
2 1 4
2 6 10

Output

854873249
469363035
566114207