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 mod = 1e9 + 7;
const int MAXN = 1e5 + 10;
const int MAXK = 5 + 1;
long long sumv[MAXK][MAXN << 2], setv[MAXN << 2];
long long prefix[MAXK][MAXN], C[MAXK][MAXK];
void Pushdown(int o, int lft, int rht) {
  if (setv[o] != -1) {
    setv[(o << 1)] = setv[(o << 1 | 1)] = setv[o];
    int mid = lft + rht >> 1;
    for (int k = 0; k < MAXK; ++k) {
      sumv[k][(o << 1)] =
          setv[(o << 1)] * (prefix[k][mid] - prefix[k][lft - 1] + mod) % mod;
      sumv[k][(o << 1 | 1)] =
          setv[(o << 1 | 1)] * (prefix[k][rht] - prefix[k][mid] + mod) % mod;
    }
    setv[o] = -1;
  }
}
void Pushup(int o) {
  for (int k = 0; k < MAXK; ++k)
    sumv[k][o] = sumv[k][(o << 1)] + sumv[k][(o << 1 | 1)];
}
void Build(int o, int lft, int rht) {
  if (lft == rht) {
    scanf("%lld", setv + o);
    sumv[0][o] = setv[o] % mod;
    for (int k = 1; k < MAXK; ++k) sumv[k][o] = sumv[k - 1][o] * lft % mod;
  } else {
    int mid = lft + rht >> 1;
    Build((o << 1), lft, mid);
    Build((o << 1 | 1), mid + 1, rht);
    Pushup(o);
  }
}
int ul, ur, uv;
void Update(int o, int lft, int rht) {
  if (ul <= lft and rht <= ur) {
    setv[o] = uv;
    for (int k = 0; k < MAXK; ++k)
      sumv[k][o] = setv[o] * (prefix[k][rht] - prefix[k][lft - 1] + mod) % mod;
  } else {
    Pushdown(o, lft, rht);
    int mid = lft + rht >> 1;
    if (ul <= mid) Update((o << 1), lft, mid);
    if (ur > mid) Update((o << 1 | 1), mid + 1, rht);
    Pushup(o);
  }
}
int ql, qr, qk;
long long Query(int o, int lft, int rht) {
  if (ql <= lft and rht <= qr) return sumv[qk][o];
  Pushdown(o, lft, rht);
  int mid = lft + rht >> 1;
  long long ans = 0;
  if (ql <= mid) ans += Query((o << 1), lft, mid);
  if (qr > mid) ans += Query((o << 1 | 1), mid + 1, rht);
  return ans % mod;
}
void work() {
  for (int i = 0; i < MAXK; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  for (int i = 1; i < MAXN; ++i) {
    long long u = 1;
    for (int k = 0; k < MAXK; ++k) {
      prefix[k][i] = (prefix[k][i - 1] + u) % mod;
      u = u * i % mod;
    }
  }
  int N, Q, K;
  char cmd[20];
  long long ans, ret;
  scanf("%d%d", &N, &Q);
  memset(setv, -1, sizeof setv);
  Build(1, 1, N);
  while (Q--) {
    scanf("%s", cmd);
    switch (cmd[0]) {
      case '?':
        scanf("%d%d%d", &ql, &qr, &K);
        ans = 0;
        ret = 1;
        for (qk = K; qk >= 0; --qk, ret = ret * (1 - ql) % mod)
          ans += Query(1, 1, N) * (ret) % mod * C[K][qk] % mod;
        printf("%lld\n", (ans % mod + mod) % mod);
        break;
      case '=':
        scanf("%d%d%d", &ul, &ur, &uv);
        Update(1, 1, N);
        break;
    }
  }
}
int main() {
  work();
  return 0;
}