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>
const int C = 1000000007;
const int M = 100010;
const int K = 6;
const long long c[K][K] = {1, 0,  0, 0,  0, 0, 1, -1, 0,  0,   0, 0,
                           1, -2, 1, 0,  0, 0, 1, -3, 3,  -1,  0, 0,
                           1, -4, 6, -4, 1, 0, 1, -5, 10, -10, 5, -1};
struct V {
  int v[K];
  V() { memset(v, 0, sizeof(v)); }
  int operator[](const int &i) const { return v[i]; }
  V operator+(const V &b) const {
    V ret;
    for (int i = 0; i < K; i++) ret.v[i] = (v[i] + b.v[i]) % C;
    return ret;
  }
  V operator*(const int &b) const {
    V ret;
    for (int i = 0; i < K; i++) ret.v[i] = (long long)v[i] * b % C;
    return ret;
  }
  void init(int x) {
    v[0] = 1;
    for (int j = 1; j < K; j++) v[j] = (long long)v[j - 1] * x % C;
  }
};
struct P {
  V a, i;
  int l, r, lz;
  P *lch, *rch;
  P(int _l, int _r) : l(_l), r(_r), lz(-1), lch(0), rch(0) {}
  void modify(int v) { a = i * (lz = v); }
  void down() {
    if (lz != -1) lch->modify(lz), rch->modify(lz), lz = -1;
  }
  void update_i() { i = lch->i + rch->i; }
  void update_a() { a = lch->a + rch->a; }
} * root;
int v[M];
void build(P *&p, int l, int r) {
  p = new P(l, r);
  if (l == r) {
    p->i.init(l), p->a = p->i * v[l];
    return;
  }
  int mi = l + r >> 1;
  build(p->lch, l, mi), build(p->rch, mi + 1, r);
  p->update_i(), p->update_a();
}
void modify(P *p, int l, int r, int x) {
  if (!p) return;
  if (p->l > r || p->r < l) return;
  if (p->l >= l && p->r <= r) {
    p->modify(x);
    return;
  }
  p->down();
  modify(p->lch, l, r, x), modify(p->rch, l, r, x);
  p->update_a();
}
V query(P *p, int l, int r) {
  if (!p) return V();
  if (p->l > r || p->r < l) return V();
  if (p->l >= l && p->r <= r) return p->a;
  p->down();
  return query(p->lch, l, r) + query(p->rch, l, r);
}
int query(int l, int r, int k) {
  V a = query(root, l, r);
  V x;
  x.init(l - 1);
  int ret = 0;
  for (int j = 0; j <= k; j++)
    ret = ((ret + c[k][j] * a[k - j] % C * x[j]) % C + C) % C;
  return ret;
}
int main() {
  int n, m, l, r, x;
  char op[2];
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
  build(root, 1, n);
  for (int i = 1; i <= m; i++) {
    scanf("%s%d%d%d", op, &l, &r, &x);
    if (op[0] == '=')
      modify(root, l, r, x);
    else
      printf("%d\n", query(l, r, x));
  }
  return 0;
}