|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
H - Queries with recurrences
Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (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