A8778 | More Queries to Array...

You've got an array, consisting of $n$ integers: $a_{1},a_{2},...,a_{n}$ . Your task is to quickly run the queries of two types:

1. 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$ .
2. Calculate and print sum , where $k$ doesn't exceed $5$ . As the value of the sum can be rather large, you should print it modulo $1000000007 (10^{9}+7)$ .

The first line contains two integers $n$ and $m$ ( $1<=n,m<=10^{5}$ ), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains $n$ integers: $a_{1},a_{2},...,a_{n}$ ( $0<=a_{i}<=10^{9}$ ) — the initial values of the array elements.

Then $m$ queries follow, one per line:

1. The assign query has the following format: "", ( $1<=l<=r<=n; 0<=x<=10^{9}$ ).
2. The query to calculate the sum has the following format: "", ( $1<=l<=r<=n; 0<=k<=5$ ).

All numbers in the input are integers.

For each query to calculate the sum print an integer — the required sum modulo $1000000007 (10^{9}+7)$ .