Starlight Queries

Mayuri has (n) stars, each with an initial brightness (A_i). She frequently wonders what the total brightness is over an interval ([l, r]). However, since the stars blink, their brightness can change over time. There are two types of operations:

1. Update Operation: Given three integers (y), (x), and (z) (with the guarantee that (y \leq x)), increase the brightness of stars at indices of the form (y, y+x, y+2x, \ldots) by (z).

2. Query Operation: Given two integers (l) and (r), report the sum (\sum_{i=l}^{r} A_i) modulo (10^{9}+7).

Your task is to process (q) operations (updates and queries) in the order they are given and for each query operation output the result modulo (10^{9}+7).

inputFormat

The first line contains two integers (n) and (q) — the number of stars and the number of operations, respectively. The next line contains (n) integers (A_1, A_2, \ldots, A_n) denoting the initial brightness of the stars. Each of the following (q) lines describes an operation in one of the following formats:

• Update Operation: 1 y x z (Increase the brightness of stars at indices (y, y+x, y+2x, \ldots) by (z). It is guaranteed that (y \leq x).)

• Query Operation: 2 l r (Output the sum of brightness (\sum_{i=l}^{r} A_i) modulo (10^{9}+7)).

All indices are 1-indexed.

outputFormat

For each query operation (operations of type 2), output a single integer on a new line — the sum of brightness from index (l) to (r) modulo (10^{9}+7).

sample

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

15
10