Mayuri has $n$ stars, each with a brightness $A_{i}$. Mayuri often wants to know the sum of the brightness of all stars in a range $[l, r]$. However, stars blink, so their brightness changes. Sometimes, the brightness of stars at 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 mathematics, so please answer her queries. The answer should be taken modulo $10^{9}+7$.

Input

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

The next line contains $n$ integers $A_{i}$, representing the initial brightness.

The next $m$ lines each start with an integer representing the operation type. If the type is $1$, it is an update operation, followed by three integers $x, y, z$. If the type is $2$, it is a query operation, followed by two integers $l, r$.

Output

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

Examples

Input 1

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

Output 1

9
12
9
13

Note

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

For $10\%$ of the data, $n, m \leq 1000$.

For another $10\%$ of the data, $x > 1000$.

For another $10\%$ of the data, $x > 300$.

For another $10\%$ of the data, $n, m \leq 10^5$.

For $100\%$ of the data, $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$.