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>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;
const int maxn = (int)1e5 + 10;
int pp[4 * maxn];
int a[maxn], c[6][6], pw[maxn][6], pref[maxn][6];
struct node {
  int cnt;
  int sum[6];
  node() {
    cnt = 0;
    memset(sum, 0, sizeof(sum));
  }
  node(int cntt) {
    cnt = cntt;
    memset(sum, 0, sizeof(sum));
  }
} t[4 * maxn];
void push(int idx, int l, int m, int r) {
  if (pp[idx] != -1) {
    pp[2 * idx] = pp[idx];
    pp[2 * idx + 1] = pp[idx];
    for (int i = 0; i <= 5; i++) {
      t[2 * idx].sum[i] = (long long)pref[m - l + 1][i] * pp[idx] % mod;
      t[2 * idx + 1].sum[i] = (long long)pref[r - m][i] * pp[idx] % mod;
    }
    pp[idx] = -1;
  }
}
void make(int idx) {
  t[idx].cnt = t[2 * idx].cnt + t[2 * idx + 1].cnt;
  for (int i = 0; i <= 5; i++) {
    t[idx].sum[i] = t[2 * idx].sum[i];
    for (int j = i; j >= 0; j--) {
      t[idx].sum[i] +=
          (long long)((long long)t[2 * idx + 1].sum[i - j] * c[i][j] % mod) *
          pw[t[2 * idx].cnt][j] % mod;
      t[idx].sum[i] %= mod;
    }
  }
}
void build(int l, int r, int idx) {
  if (l == r) {
    t[idx].cnt = 1;
    for (int i = 0; i <= 5; i++) {
      t[idx].sum[i] = a[l];
    }
  } else {
    int m = (l + r) >> 1;
    build(l, m, 2 * idx);
    build(m + 1, r, 2 * idx + 1);
    make(idx);
  }
}
void put(int l, int r, int a, int b, int val, int idx) {
  if (b < l || r < a) return;
  if (a <= l && r <= b) {
    pp[idx] = val;
    for (int i = 0; i <= 5; i++) {
      t[idx].sum[i] = (long long)pref[r - l + 1][i] * val % mod;
    }
  } else {
    int m = (l + r) >> 1;
    push(idx, l, m, r);
    put(l, m, a, b, val, 2 * idx);
    put(m + 1, r, a, b, val, 2 * idx + 1);
    make(idx);
  }
}
node make(node lf, node rg) {
  if (lf.cnt == 0) return rg;
  if (rg.cnt == 0) return lf;
  node res = lf;
  res.cnt += rg.cnt;
  for (int i = 0; i <= 5; i++) {
    for (int j = i; j >= 0; j--) {
      res.sum[i] += (long long)((long long)rg.sum[i - j] * c[i][j] % mod) *
                    pw[lf.cnt][j] % mod;
      res.sum[i] %= mod;
    }
  }
  return res;
}
node get(int l, int r, int a, int b, int idx) {
  if (b < l || r < a) return node(0);
  if (a <= l && r <= b) return t[idx];
  int m = (l + r) >> 1;
  push(idx, l, m, r);
  node lf = get(l, m, a, b, 2 * idx);
  node rg = get(m + 1, r, a, b, 2 * idx + 1);
  return make(lf, rg);
}
int main() {
  memset(pp, -1, sizeof(pp));
  for (int i = 1; i < maxn; i++) {
    pw[i][0] = 1;
    for (int j = 1; j <= 5; j++) {
      pw[i][j] = (long long)pw[i][j - 1] * i % mod;
    }
    for (int j = 0; j <= 5; j++) {
      pref[i][j] = pref[i - 1][j] + pw[i][j];
      pref[i][j] %= mod;
    }
  }
  for (int i = 0; i <= 5; i++) {
    c[i][0] = 1;
  }
  for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
  }
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  build(0, n - 1, 1);
  int l, r, x;
  char s[11];
  for (int i = 0; i < m; i++) {
    scanf("%s%d%d%d", s, &l, &r, &x);
    --l;
    --r;
    if (s[0] == '=') {
      put(0, n - 1, l, r, x, 1);
    } else {
      printf("%d\n", get(0, n - 1, l, r, 1).sum[x]);
    }
  }
  return 0;
}