你有一个数组,由 n 个整数组成:a1,a2,...,an。您的任务是快速运行两种类型的查询:
1. 将值 x 分配给从 l 到 r(含)的所有元素。经过这样的查询,数组 al, al + 1, ..., ar 的元素值等于 x。
2. 计算并打印总和 $$\sum_{i=l}^{r} a_i \cdot (i-l+1)^k$$,其中 k 不超过 5。由于总和的值可能相当大,因此您应该打印它模 1000000007 (109 + 7)。
输入
第一行包含两个整数n和m(1≤n,m≤105),分别表示数组中有多少个数字以及查询的次数。第二行包含 n 个整数:a1, a2, ..., an (0 ≤ ai ≤ 109) — 数组元素的初始值。
接下来是 m 个查询,每行一个:
1. 分配查询的格式如下:“$$l r x$$”, (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109)。
2. 计算总和的查询格式如下:“$$? l r k$$”, (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5)。
输入中的所有数字均为整数。
输出
对于每个计算总和的查询,打印一个整数 — 所需总和模 1000000007 (109 + 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