Description

Mayuri has $n$ stars, each with a brightness $A_{i}$. Mayuri often wants to know the sum of the brightnesses of all stars in an interval $[l, r]$. But stars twinkle, so their brightness can change. At times, the brightness of stars with indices $y, y+x, y+2x, y+3x, \ldots, y+kx$ increases by $z$. It is guaranteed that $y \leq x$.

Mayuri is not very good at math; please answer her queries. The answer should be taken modulo $10^{9}+7$.

Input Format

The first line contains two integers $n$ and $m$, the number of stars and the number of operations.

The next line contains $n$ numbers $A_{i}$, the initial brightness values.

Then follow $m$ lines. Each line starts with an integer denoting the operation type: if it is $1$, it is an update, followed by three integers $x, y, z$; if it is $2$, it is a query, followed by two integers $l, r$.

Output Format

For each query operation, output one line with the answer.

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

9
12
9
13

Hint

Idea: yanQval, Solution: yanQval, Code: yanQval, Data: yanQval & nzhtl1477.

Constraints:

• For $10\%$ of the testdata, $n, m \leq 1000$.
• For another $10\%$ of the testdata, $x>1000$.
• For another $10\%$ of the testdata, $x>300$.
• For another $10\%$ of the testdata, $n, m \leq 10^5$.
• For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^5$, $1 \leq y \leq x \leq n$, $1 \leq l \leq r \leq n$, $0 \leq A_i, z \leq 10^{9}+7$.

Translated by ChatGPT 5