More Queries to Array...

题意翻译

一段序列$ 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

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

3 1
1000000000 1000000000 1000000000
? 1 3 0

输出样例 #2

999999986