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)$.

Input

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.

Output

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