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 N = 100100;
const long long mod = 1e9 + 7;
long long n, m;
long long a[N];
long long sum[N][6];
long long c[6][6];
void init() {
  for (long long i = 1; i < N; i++) {
    long long tmp = 1;
    for (long long j = 0; j < 6; j++) {
      sum[i][j] = (sum[i - 1][j] + tmp) % mod;
      tmp = (tmp * i) % mod;
    }
  }
  for (int i = 0; i < 6; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
}
struct Seg {
  long long sum[6];
  long long set;
} seg[N << 4];
void push_up(int rt) {
  for (int i = 0; i < 6; i++)
    seg[rt].sum[i] = seg[rt << 1].sum[i] + seg[rt << 1 | 1].sum[i];
}
void build(int l, int r, int rt) {
  seg[rt].set = -1;
  if (l == r) {
    for (int i = 0; i < 6; i++) {
      long long tmp = (sum[l][i] - sum[l - 1][i] + mod) % mod;
      seg[rt].sum[i] = a[l] * tmp % mod;
    }
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  push_up(rt);
}
void maintain(int l, int r, int rt, long long v) {
  for (int i = 0; i < 6; i++) {
    long long tmp = (sum[r][i] - sum[l - 1][i] + mod) % mod;
    seg[rt].sum[i] = v * tmp % mod;
  }
}
void push_down(int l, int r, int rt) {
  if (seg[rt].set != -1) {
    int m = (l + r) >> 1;
    maintain(l, m, rt << 1, seg[rt].set);
    maintain(m + 1, r, rt << 1 | 1, seg[rt].set);
    seg[rt << 1].set = seg[rt << 1 | 1].set = seg[rt].set;
    seg[rt].set = -1;
  }
}
void update(int L, int R, long long v, int l, int r, int rt) {
  if (L <= l && r <= R) {
    maintain(l, r, rt, v);
    seg[rt].set = v;
    return;
  }
  push_down(l, r, rt);
  int m = (l + r) >> 1;
  if (L <= m) update(L, R, v, l, m, rt << 1);
  if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
  push_up(rt);
}
long long query(int L, int R, int k, int l, int r, int rt) {
  if (L <= l && r <= R) {
    long long res = 0, tmp = 1;
    for (int i = k; i >= 0; i--) {
      res = (res + seg[rt].sum[i] * c[k][i] % mod * tmp % mod + mod) % mod;
      tmp = tmp * (1 - L) % mod;
    }
    return res;
  }
  push_down(l, r, rt);
  int m = (l + r) >> 1;
  long long res = 0;
  if (L <= m) res = (res + query(L, R, k, l, m, rt << 1)) % mod;
  if (R > m) res = (res + query(L, R, k, m + 1, r, rt << 1 | 1)) % mod;
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  init();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);
  while (m--) {
    char op;
    long long l, r, x;
    cin >> op >> l >> r >> x;
    if (op == '=')
      update(l, r, x, 1, n, 1);
    else {
      long long ans = query(l, r, x, 1, n, 1);
      cout << ans << endl;
    }
  }
  return 0;
}