H - Queries with recurrences

Time limit: 6 s
Memory limit: 512 MiB
Languages: C, C++, Java, Python, ... (details)

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$).

Input

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$.

Output

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

Sample test(s)

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