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>
const int MOD = 1000000007, K = 5, N = 100000 + 9;
int n, L, R, V, A[N], sum[K + 1][N], C[K + 1][K + 1];
struct node {
  int a[6], l, r, tag;
  node() : l(0), r(0) {
    memset(a, 0, sizeof a);
    tag = -1;
  }
  void reset(int x, int len) {
    for (int i = 0; i <= K; ++i) a[i] = 1ll * sum[i][len] * x % MOD;
    tag = x;
  }
} a[N * 4], res;
int pow(int x, int k) {
  int res = 1;
  for (; k; k /= 2, x = 1ll * x * x % MOD)
    if (k & 1) res = 1ll * res * x % MOD;
  return res;
}
node merge(const node &lhs, const node &rhs) {
  res.l = lhs.l;
  res.r = rhs.r;
  res.a[0] = (lhs.a[0] + rhs.a[0]) % MOD;
  int len = lhs.r - lhs.l + 1;
  for (int i = 1; i <= K; ++i) {
    long long tmp = (lhs.a[i] + rhs.a[i]) % MOD;
    for (int j = 0; j < i; ++j)
      tmp += 1ll * pow(len, i - j) * C[i][j] % MOD * rhs.a[j] % MOD;
    res.a[i] = tmp % MOD;
  }
  return res;
}
inline void rls(const int id, const int len) {
  a[id * 2].reset(a[id].tag, (len + 1) / 2);
  a[id * 2 + 1].reset(a[id].tag, len / 2);
  a[id].tag = -1;
}
void modify(const int id, const int l, const int r) {
  if (L <= l && r <= R) return a[id].reset(V, r - l + 1);
  if (a[id].tag >= 0) rls(id, r - l + 1);
  const int mid = (l + r) / 2;
  if (L <= mid) modify(id * 2, l, mid);
  if (mid < R) modify(id * 2 + 1, mid + 1, r);
  a[id] = merge(a[id * 2], a[id * 2 + 1]);
}
node query(const int id, const int l, const int r) {
  if (L <= l && r <= R) return a[id];
  if (a[id].tag >= 0) rls(id, r - l + 1);
  const int mid = (l + r) / 2;
  node res;
  if (R <= mid)
    res = query(id * 2, l, mid);
  else if (mid < L)
    res = query(id * 2 + 1, mid + 1, r);
  else
    res = merge(query(id * 2, l, mid), query(id * 2 + 1, mid + 1, r));
  return res;
}
void build(const int id, const int l, const int r) {
  if (l == r) {
    a[id].l = l;
    a[id].r = r;
    return a[id].reset(A[l], 1);
  }
  const int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
  a[id] = merge(a[id * 2], a[id * 2 + 1]);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    for (int j = 0, tmp = 1; j <= K; ++j, tmp = 1ll * tmp * i % MOD)
      sum[j][i] = (sum[j][i - 1] + tmp) % MOD;
  C[0][0] = 1;
  for (int i = 1; i <= K; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
  for (int i = 1; i <= n; ++i) scanf("%d", A + i);
  build(1, 1, n);
  while (m--) {
    char c;
    int x;
    scanf("\n%c%d%d%d", &c, &L, &R, &x);
    V = x;
    if (c == '=')
      modify(1, 1, n);
    else {
      node tmp = query(1, 1, n);
      int ans = tmp.a[x];
      printf("%d\n", ans);
    }
  }
}