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 long long mod = 1000000007LL;
struct stree {
  int l, r, mid;
  long long s[6];
  int c;
} a[100005 * 4];
int s[100005];
long long fac[100005][6];
long long ss[100005][6], com[100005][6];
void init() {
  for (int i = 1; i < 100005; i++) {
    fac[i][0] = 1;
    ss[i][0] = i;
    for (int j = 1; j <= 5; j++) {
      fac[i][j] = fac[i][j - 1] * i;
      fac[i][j] %= mod;
      ss[i][j] = ss[i - 1][j] + fac[i][j];
    }
  }
  com[1][1] = com[1][0] = 1;
  com[0][0] = 1;
  for (int i = 2; i < 100005; i++) {
    com[i][0] = 1;
    for (int j = 1; j <= 5; j++)
      com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % mod;
  }
}
void push_up(int p) {
  for (int i = 0; i <= 5; i++) {
    a[p].s[i] = a[p * 2].s[i] + a[p * 2 + 1].s[i];
    a[p].s[i] %= mod;
  }
}
void push_down(int p) {
  if (a[p].c == -1) return;
  int x = a[p].c;
  for (int i = 0; i <= 5; i++) {
    a[p * 2].s[i] =
        ((long long)(x) *
         ((ss[a[p * 2].r][i] - ss[a[p * 2].l - 1][i] + mod) % mod)) %
        mod;
    a[p * 2 + 1].s[i] =
        ((long long)(x) *
         ((ss[a[p * 2 + 1].r][i] - ss[a[p * 2 + 1].l - 1][i] + mod) % mod)) %
        mod;
  }
  a[p * 2].c = a[p * 2 + 1].c = a[p].c;
  a[p].c = -1;
}
void create(int l, int r, int p) {
  a[p].l = l;
  a[p].r = r;
  for (int i = 0; i <= 5; i++) a[p].s[i] = 0;
  a[p].c = -1;
  if (l == r) {
    for (int i = 0; i <= 5; i++) {
      a[p].s[i] = s[l] * fac[l][i];
      a[p].s[i] %= mod;
    }
    return;
  }
  int mid = (l + r) >> 1;
  create(l, mid, p * 2);
  create(mid + 1, r, p * 2 + 1);
  push_up(p);
}
void update(int l, int r, int x, int p) {
  if (a[p].l == l && a[p].r == r) {
    a[p].c = x;
    for (int i = 0; i <= 5; i++) {
      a[p].s[i] =
          ((long long)(x) * ((ss[r][i] - ss[l - 1][i] + mod) % mod)) % mod;
    }
    return;
  }
  push_down(p);
  int mid = (a[p].l + a[p].r) >> 1;
  if (r <= mid)
    update(l, r, x, p * 2);
  else if (l > mid)
    update(l, r, x, p * 2 + 1);
  else {
    update(l, mid, x, p * 2);
    update(mid + 1, r, x, p * 2 + 1);
  }
  push_up(p);
}
long long query(int l, int r, int k, int p) {
  if (a[p].l == l && a[p].r == r) {
    return a[p].s[k];
  }
  push_down(p);
  int mid = (a[p].r + a[p].l) >> 1;
  if (r <= mid)
    return query(l, r, k, p * 2);
  else if (l > mid)
    return query(l, r, k, p * 2 + 1);
  else {
    return (query(l, mid, k, p * 2) + query(mid + 1, r, k, p * 2 + 1)) % mod;
  }
}
int n, m;
int main() {
  init();
  while (scanf("%d %d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &s[i]);
    }
    create(1, n, 1);
    char str[10];
    int l, r, x;
    for (int i = 1; i <= m; i++) {
      scanf("%s %d %d %d", str, &l, &r, &x);
      if (str[0] == '=') {
        update(l, r, x, 1);
      } else {
        long long t = 1, ans = 0;
        for (int i = x; i >= 0; i--) {
          ans += ((query(l, r, i, 1) * com[x][i]) % mod * t);
          ans %= mod;
          if (ans < 0) ans += mod;
          t *= (-(l - 1));
          t %= mod;
        }
        printf("%I64d\n", ans);
      }
    }
  }
  return 0;
}