题面翻译

一段序列$a_1,a_2......a_n$
两种操作：
$=\ l\ r\ x\$表示将区间$[l,r]$的值赋为$x$
$?\ l\ r\ k\$表示输出$\Sigma_{i=l}^ra_i(i-l+1)^k\%1e9+7$ Translated by @Fheiwn

题目描述

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

样例 #1

样例输入 #1

4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5

样例输出 #1

25
43
1300

样例 #2

样例输入 #2

3 1
1000000000 1000000000 1000000000
? 1 3 0

样例输出 #2

999999986