CF266E.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 (109 + 7).

你有一个包含 $ n $ 个整数的数组：$ a_1,,a_2,,\dots,,a_n $。你需要快速处理两类查询：

1. 将区间 $[l,\,r]$（含端点）内所有元素赋值为 $ x $。执行该查询后，数组元素 $ a_l,,a_{l+1},,\dots,,a_r $ 的值均变为 $ x $。
2. 计算并输出和式 ，其中 $ k $ 不超过 5。由于该和式的值可能很大，你应输出其对 $ 1000000007 $（即 $ 10^9 + 7 $）取模的结果。

The first line contains two integers n and m (1 ≤ n, m ≤ 105), 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 ≤ 109) — 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 ≤ 109).
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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示数组中数字的个数以及查询的个数。
第二行包含 $n$ 个整数：$a_1,\ a_2,\ \dots,\ a_n$（$0 \leq a_i \leq 10^9$）—— 数组元素的初始值。

接下来是 $m$ 个查询，每行一个：

1. 赋值查询格式为：，其中 $1 \leq l \leq r \leq n$，$0 \leq x \leq 10^9$。
2. 求和查询格式为：，其中 $1 \leq l \leq r \leq n$，$0 \leq k \leq 5$。

输入中的所有数字均为整数。

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

对于每个计算和的查询，输出一个整数——该和对 1000000007（$10^9 + 7$）取模的结果。