Problem: You've got an array, consisting of n integers: a1, a2, ..., an. 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 al, al + 1, ..., ar become equal to x.
  2. Calculate and print sum <image>, where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (109 + 7).

Input

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: a1, a2, ..., an (0 ≤ ai ≤ 109) — the initial values of the array elements.

Then m queries follow, one per line:

  1. The assign query has the following format: "<image>", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109).
  2. The query to calculate the sum has the following format: "<image>", (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 (109 + 7).

Examples

Input

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


Output

25
43
1300


Input

3 1
1000000000 1000000000 1000000000
? 1 3 0


Output

999999986

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int mod = 1000000007;
long long p[6][maxn], s[6][maxn];
int c[10][10];
int n, m;
int a[maxn];
struct segtree {
  int sum[6][maxn << 2];
  long long flag[maxn << 2];
  long long Pow(int a, int b) {
    long long ans = 1;
    for (int i = 1; i <= b; i++) ans = ans * a % mod;
    return ans;
  }
  void init() {
    c[0][0] = 1;
    for (int i = 1; i < 6; i++) {
      c[i][i] = 1;
      for (int j = 0; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
    for (int i = 1; i < maxn; i++)
      for (int j = 0; j < 6; j++) p[j][i] = Pow(i, j);
    for (int i = 1; i < maxn; i++)
      for (int j = 0; j < 6; j++) s[j][i] = (s[j][i - 1] + p[j][i]) % mod;
  }
  void build(int l, int r, int rt) {
    flag[rt] = -1;
    if (l == r) {
      for (int i = 0; i < 6; i++) sum[i][rt] = p[i][l] * a[l] % mod;
    } else {
      int m = (l + r) >> 1;
      build(l, m, rt << 1);
      build(m + 1, r, rt << 1 | 1);
      pushup(rt);
    }
  }
  void pushdown(int rt, int l, int r) {
    int m = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
    if (~flag[rt]) {
      for (int i = 0; i < 6; i++) {
        sum[i][ls] = (flag[rt] * (s[i][m] - s[i][l - 1]) % mod + mod) % mod;
        sum[i][rs] = (flag[rt] * (s[i][r] - s[i][m]) % mod + mod) % mod;
      }
      flag[ls] = flag[rs] = flag[rt];
      flag[rt] = -1;
    }
  }
  void pushup(int rt) {
    int ls = rt << 1, rs = rt << 1 | 1;
    for (int i = 0; i < 6; i++) sum[i][rt] = (sum[i][ls] + sum[i][rs]) % mod;
  }
  void update(int L, int R, int val, int l, int r, int rt) {
    if (L <= l && r <= R) {
      flag[rt] = val;
      for (int i = 0; i < 6; i++)
        sum[i][rt] = (flag[rt] * (s[i][r] - s[i][l - 1]) % mod + mod) % mod;
      return;
    }
    pushdown(rt, l, r);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, val, l, m, rt << 1);
    if (R > m) update(L, R, val, m + 1, r, rt << 1 | 1);
    pushup(rt);
  }
  int query(int L, int R, int dem, int l, int r, int rt) {
    if (L <= l && r <= R) {
      return sum[dem][rt];
    }
    pushdown(rt, l, r);
    int m = (l + r) >> 1;
    int ans = 0;
    if (L <= m) ans = (ans + query(L, R, dem, l, m, rt << 1)) % mod;
    if (R > m) ans = (ans + query(L, R, dem, m + 1, r, rt << 1 | 1)) % mod;
    return ans;
  }
} st;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  st.init();
  st.build(1, n, 1);
  char op[5];
  int l, r, k;
  while (m--) {
    scanf("%s", op);
    scanf("%d%d%d", &l, &r, &k);
    if (op[0] == '?') {
      long long ans = 0;
      long long tmp = 1;
      for (int i = 0; i <= k; i++) {
        ans += (long long)st.query(l, r, k - i, 1, n, 1) * c[k][i] % mod * tmp %
               mod;
        ans %= mod;
        tmp = tmp * (1 - l) % mod;
      }
      printf("%I64d\n", (ans + mod) % mod);
    } else {
      st.update(l, r, k, 1, n, 1);
    }
  }
  return 0;
}