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 N = 1e5 + 9, mod = 1e9 + 7, Mod = mod;
int n, m;
int ar[N];
struct D {
  long long s[6];
};
struct node {
  int l, r;
  long long lz;
  D it;
  long long num() { return r - l + 1; }
} t[N << 2];
long long tri[10][10];
long long sum[N][6], pi[N][6];
void pre() {
  tri[0][0] = 1;
  for (int i = 1; i < 6; i++) {
    tri[i][0] = 1;
    for (int j = 1; j <= i; j++) tri[i][j] = tri[i - 1][j] + tri[i - 1][j - 1];
  }
  for (int i = 1; i < N; i++) {
    sum[i][0] = 1;
    pi[i][0] = 1;
    for (int j = 1; j < 6; j++)
      sum[i][j] = (sum[i][j - 1] * i) % mod, pi[i][j] = sum[i][j];
    for (int j = 0; j < 6; j++) sum[i][j] = (sum[i][j] + sum[i - 1][j]) % mod;
  }
}
void push_up(int p) {
  for (int i = 0; i < 6; i++) {
    t[p].it.s[i] = t[(p << 1)].it.s[i];
    for (int j = i; j >= 0; j--) {
      t[p].it.s[i] = (t[p].it.s[i] + tri[i][j] * pi[t[(p << 1)].num()][i - j] %
                                         mod * t[((p << 1) | 1)].it.s[j] % mod);
      if (t[p].it.s[i] >= mod) t[p].it.s[i] -= mod;
    }
  }
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  t[p].lz = -1;
  if (l == r) {
    for (int i = 0; i < 6; i++) t[p].it.s[i] = ar[l];
    return;
  }
  int mid = ((t[p].l + t[p].r) >> 1);
  build((p << 1), l, mid);
  build(((p << 1) | 1), mid + 1, r);
  push_up(p);
}
void push_down(int p) {
  long long &dp = t[p].lz;
  if (dp + 1) {
    t[(p << 1)].lz = t[((p << 1) | 1)].lz = dp;
    for (int i = 0; i < 6; i++) {
      t[(p << 1)].it.s[i] = dp * sum[t[(p << 1)].num()][i] % mod;
      t[((p << 1) | 1)].it.s[i] = dp * sum[t[((p << 1) | 1)].num()][i] % mod;
    }
    dp = -1;
  }
}
void modify(int p, int l, int r, long long v) {
  if (t[p].l == l && t[p].r == r) {
    for (int i = 0; i < 6; i++) t[p].it.s[i] = v * sum[t[p].num()][i] % mod;
    t[p].lz = v;
    return;
  }
  push_down(p);
  int mid = ((t[p].l + t[p].r) >> 1);
  if (r <= mid)
    modify((p << 1), l, r, v);
  else if (l > mid)
    modify(((p << 1) | 1), l, r, v);
  else
    modify((p << 1), l, mid, v), modify(((p << 1) | 1), mid + 1, r, v);
  push_up(p);
}
D query(int p, int l, int r, int k) {
  if (t[p].l == l && t[p].r == r) {
    return t[p].it;
  }
  push_down(p);
  int mid = ((t[p].l + t[p].r) >> 1);
  if (r <= mid)
    return query((p << 1), l, r, k);
  else if (l > mid)
    return query(((p << 1) | 1), l, r, k);
  else {
    D bef = query((p << 1), l, mid, k),
      aft = query(((p << 1) | 1), mid + 1, r, k);
    int len = mid + 1 - l;
    for (int i = 0; i <= k; i++) {
      for (int j = i; j + 1; j--) {
        bef.s[i] =
            (bef.s[i] + pi[len][i - j] * tri[i][j] % mod * aft.s[j] % mod);
        if (bef.s[i] >= mod) bef.s[i] -= mod;
      }
    }
    return bef;
  }
}
int main() {
  pre();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", ar + i);
  }
  build(1, 1, n);
  char ss[10];
  int l, r, x;
  while (m--) {
    scanf("%s%d%d%d", ss, &l, &r, &x);
    if (ss[0] == '=')
      modify(1, l, r, x);
    else {
      D ans = query(1, l, r, x);
      printf("%d\n", (int)ans.s[x]);
    }
  }
  return 0;
}