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 + 5, mo = 1e9 + 7;
const int C[7][7] = {{1, 0, 0, 0, 0, 0, 0},   {1, 1, 0, 0, 0, 0, 0},
                     {1, 2, 1, 0, 0, 0, 0},   {1, 3, 3, 1, 0, 0, 0},
                     {1, 4, 6, 4, 1, 0, 0},   {1, 5, 10, 10, 5, 1, 0},
                     {1, 6, 15, 20, 15, 6, 1}};
const int rev[7] = {0,         1,         500000004, 333333336,
                    250000002, 400000003, 166666668};
struct NODE {
  int val[6], pas;
  NODE() : pas(-1) { memset(val, 0, sizeof val); }
};
int N, M;
long long s[6];
NODE f[maxn << 1];
void Ins(int l, int r, int ql, int qr, int x) {
  int mid((l + r) >> 1), now((((l) + (r)) | ((l) != (r)))),
      son1((((l) + (mid)) | ((l) != (mid)))),
      son2((((mid + 1) + (r)) | ((mid + 1) != (r))));
  if (l == ql && r == qr) {
    int R(r + 1), L(l);
    s[0] = R - L;
    for (int i = 1; i <= 5; i++) {
      R = (long long)R * (r + 1) % mo, L = (long long)L * l % mo;
      s[i] = R - L;
      for (int j = 0; j < i; j++) s[i] -= s[j] * C[i + 1][j];
      s[i] = (s[i] % mo * rev[i + 1] % mo + mo) % mo;
    }
    for (int i = 0; i <= 5; i++) f[now].val[i] = s[i] * x % mo;
    f[now].pas = x;
    return;
  }
  if (~f[now].pas) {
    Ins(l, mid, l, mid, f[now].pas);
    Ins(mid + 1, r, mid + 1, r, f[now].pas);
    f[now].pas = -1;
  }
  if (qr <= mid)
    Ins(l, mid, ql, qr, x);
  else if (ql > mid)
    Ins(mid + 1, r, ql, qr, x);
  else
    Ins(l, mid, ql, mid, x), Ins(mid + 1, r, mid + 1, qr, x);
  for (int i = 0; i <= 5; i++)
    f[now].val[i] = (f[son1].val[i] + f[son2].val[i]) % mo;
}
int Find(int l, int r, int ql, int qr, int L, int x) {
  int mid((l + r) >> 1), now((((l) + (r)) | ((l) != (r))));
  if (l == ql && r == qr) {
    long long ret(0), p(1);
    for (int i = x, k = 1; i >= 0; i--, k = -k, p = p * L % mo)
      ret += (long long)k * C[x][i] * f[now].val[i] % mo * p % mo;
    return (ret % mo + mo) % mo;
  }
  if (~f[now].pas) {
    Ins(l, mid, l, mid, f[now].pas);
    Ins(mid + 1, r, mid + 1, r, f[now].pas);
    f[now].pas = -1;
  }
  if (qr <= mid) return Find(l, mid, ql, qr, L, x);
  if (ql > mid) return Find(mid + 1, r, ql, qr, L, x);
  return (Find(l, mid, ql, mid, L, x) + Find(mid + 1, r, mid + 1, qr, L, x)) %
         mo;
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) {
    int x;
    scanf("%d", &x);
    Ins(1, N, i, i, x);
  }
  for (int i = 1; i <= M; i++) {
    char type;
    int l, r, x;
    scanf(" %c%d%d%d", &type, &l, &r, &x);
    if (type == '=')
      Ins(1, N, l, r, x);
    else
      printf("%d\n", Find(1, N, l, r, l - 1, x));
  }
  return 0;
}