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 maxn = 1e5 + 10;
const long long mod = 1e9 + 7;
int C[10][10];
int n, m;
long long a[maxn];
long long s[maxn][10];
struct Node {
  int lazy;
  long long sum[7];
} node[maxn << 2];
long long quick_pow(long long a, long long n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = ans * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}
void init() {
  for (int i = 0; i <= 5; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
  }
  for (int i = 0; i < 100005; i++) {
    s[i][0] = 0;
    for (int j = 0; j <= 5; j++) {
      if (i >= 1) s[i][j] = (s[i - 1][j] + quick_pow(i, j)) % mod;
    }
  }
}
void PushUp(int root) {
  for (int i = 0; i <= 5; i++) {
    node[root].sum[i] =
        (node[root << 1].sum[i] + node[root << 1 | 1].sum[i]) % mod;
  }
}
void PushDown(int root, int l, int r) {
  if (~node[root].lazy) {
    int mid = (l + r) >> 1;
    node[root << 1].lazy = node[root].lazy;
    node[root << 1 | 1].lazy = node[root].lazy;
    for (int i = 0; i <= 5; i++) {
      node[root << 1].sum[i] =
          (s[mid][i] - s[l - 1][i] + mod) % mod * node[root << 1].lazy % mod;
      node[root << 1 | 1].sum[i] =
          (s[r][i] - s[mid][i] + mod) % mod * node[root << 1 | 1].lazy % mod;
    }
    node[root].lazy = -1;
  }
}
void Build(int root, int l, int r) {
  node[root].lazy = -1;
  if (l == r) {
    for (int i = 0; i <= 5; i++) {
      node[root].sum[i] = a[l] * quick_pow(l, i) % mod;
    }
    return;
  }
  int mid = (l + r) >> 1;
  Build(root << 1, l, mid);
  Build(root << 1 | 1, mid + 1, r);
  PushUp(root);
}
void Update(int root, int l, int r, int xl, int xr, int x) {
  if (xl <= l && xr >= r) {
    node[root].lazy = x;
    for (int i = 0; i <= 5; i++) {
      node[root].sum[i] = (s[r][i] - s[l - 1][i] + mod) % mod * x % mod;
    }
    return;
  }
  PushDown(root, l, r);
  int mid = (l + r) >> 1;
  if (xl <= mid) Update(root << 1, l, mid, xl, xr, x);
  if (xr > mid) Update(root << 1 | 1, mid + 1, r, xl, xr, x);
  PushUp(root);
}
long long Query(int root, int l, int r, int k, int xl, int xr) {
  if (xl <= l && xr >= r) {
    long long ans = 0, tmp = 1;
    for (int i = k; i >= 0; i--) {
      ans = (ans + node[root].sum[i] * C[k][i] % mod * tmp % mod + mod) % mod;
      tmp = tmp * (1 - xl) % mod;
    }
    return ans;
  }
  PushDown(root, l, r);
  int mid = (l + r) >> 1;
  long long ans = 0;
  if (xl <= mid)
    ans = (ans + Query(root << 1, l, mid, k, xl, xr) % mod + mod) % mod;
  if (xr > mid)
    ans = (ans + Query(root << 1 | 1, mid + 1, r, k, xl, xr) % mod + mod) % mod;
  return ans;
}
int main() {
  init();
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  Build(1, 1, n);
  while (m--) {
    char ch;
    long long k;
    int l, r;
    scanf(" %c %d %d %I64d", &ch, &l, &r, &k);
    if (ch == '=')
      Update(1, 1, n, l, r, k);
    else if (ch == '?') {
      long long ans = Query(1, 1, n, k, l, r);
      printf("%I64d\n", ans);
    }
  }
}