You've got an array, consisting of n integers: a₁, a₂, ..., a_n. Your task is to quickly run the queries of two types:

Assign value x to all elements from l to r inclusive. After such query the values of the elements of array a_l, a_l + 1, ..., a_r become equal to x.
Calculate and print sum $\text{[math]}$ , where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (10⁹ + 7).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹) — the initial values of the array elements.

Then m queries follow, one per line:

The assign query has the following format: " $\text{[math]}$ ", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 10⁹).
The query to calculate the sum has the following format: " $\text{[math]}$ ", (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5).

All numbers in the input are integers.

Output

For each query to calculate the sum print an integer — the required sum modulo 1000000007 (10⁹ + 7).

More Queries to Array...

Examples