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;
#pragma comment(linker, "/STACK:102400000,102400000")
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;
int n, m, x, L, R;
long long pre[N][6];
long long sum[N << 2][6];
int laz[N << 2];
inline void pushup(int rt) {
  for (int i = int(0); i <= int(5); ++i)
    sum[rt][i] = sum[rt << 1][i] + sum[rt << 1 | 1][i], sum[rt][i] %= MOD;
}
inline void pushdown(int rt, int l, int r) {
  if (laz[rt] != -1) {
    int m = (l + r) >> 1;
    for (int i = int(0); i <= int(5); ++i) {
      sum[rt << 1][i] =
          ((pre[m][i] - pre[l - 1][i]) % MOD + MOD) % MOD * laz[rt] % MOD;
      sum[rt << 1 | 1][i] =
          ((pre[r][i] - pre[m][i]) % MOD + MOD) % MOD * laz[rt] % MOD;
    }
    laz[rt << 1] = laz[rt << 1 | 1] = laz[rt];
    laz[rt] = -1;
  }
}
void build(int rt, int l, int r) {
  laz[rt] = -1;
  if (l == r) {
    scanf("%d", &x);
    sum[rt][0] = (long long)x;
    for (int i = int(1); i <= int(5); ++i)
      sum[rt][i] = sum[rt][i - 1] * l % MOD;
    return;
  }
  int m = (l + r) >> 1;
  build(rt << 1, l, m);
  build(rt << 1 | 1, m + 1, r);
  pushup(rt);
}
void setv(int rt, int l, int r) {
  if (L <= l && r <= R) {
    laz[rt] = x;
    for (int i = int(0); i <= int(5); ++i) {
      sum[rt][i] = ((pre[r][i] - pre[l - 1][i]) % MOD + MOD) % MOD * x % MOD;
    }
    return;
  }
  pushdown(rt, l, r);
  int m = (l + r) >> 1;
  if (L <= m) setv(rt << 1, l, m);
  if (R > m) setv(rt << 1 | 1, m + 1, r);
  pushup(rt);
}
long long query(int d, int rt, int l, int r) {
  if (L <= l && r <= R) {
    return sum[rt][d];
  }
  pushdown(rt, l, r);
  int m = (l + r) >> 1;
  long long ret = 0;
  if (L <= m) ret += query(d, rt << 1, l, m);
  if (R > m) ret += query(d, rt << 1 | 1, m + 1, r);
  ret %= MOD;
  pushup(rt);
  return ret;
}
long long solve() {
  long long ret;
  long long u = (long long)L - 1;
  if (x == 0) ret = query(0, 1, 1, n);
  if (x == 1) {
    ret = query(1, 1, 1, n) - u * query(0, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
  if (x == 2) {
    ret = query(2, 1, 1, n) - 2LL * u * query(1, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + (long long)u * u % MOD * query(0, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
  }
  if (x == 3) {
    ret = query(3, 1, 1, n) - 3LL * u * query(2, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + 3LL * u * u % MOD * query(1, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret - u * u % MOD * u % MOD * query(0, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
  }
  if (x == 4) {
    ret = query(4, 1, 1, n) - 4LL * u * query(3, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + 6LL * u * u % MOD * query(2, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret - 4LL * u * u % MOD * u % MOD * query(1, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + u * u % MOD * u % MOD * u % MOD * query(0, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
  }
  if (x == 5) {
    ret = query(5, 1, 1, n) - 5LL * u * query(4, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + 10LL * u * u % MOD * query(3, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret - 10LL * u * u % MOD * u % MOD * query(2, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret + 5LL * u * u % MOD * u % MOD * u % MOD * query(1, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
    ret = ret -
          u * u % MOD * u % MOD * u % MOD * u % MOD * query(0, 1, 1, n) % MOD;
    ret = (ret % MOD + MOD) % MOD;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = int(1); i <= int(n); ++i) {
    long long t = 1;
    for (int j = int(0); j <= int(5); ++j) {
      pre[i][j] = pre[i - 1][j] + t, pre[i][j] %= MOD;
      t = t * i % MOD;
    }
  }
  build(1, 1, n);
  char s[5];
  for (int i = int(1); i <= int(m); ++i) {
    scanf("%s%d%d%d", s, &L, &R, &x);
    if (s[0] == '=') {
      setv(1, 1, n);
    } else {
      printf("%I64d\n", solve());
    }
  }
  return 0;
}