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 MOD = 1e9 + 7;
int n, m;
long long a[100005];
long long S[100005][6], C[6][6];
struct Node {
  int l, r;
  long long s[6], lazy;
  Node *lc, *rc;
} *tree = 0;
void print(Node *root);
void Init() {
  for (int i = 1; i <= n; i++) {
    long long x = 1;
    for (int j = 0; j <= 5; j++) {
      S[i][j] = (S[i - 1][j] + x) % MOD;
      x = x * i % MOD;
    }
  }
  for (int i = 0; i < 6; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < 6 - 1; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
}
void down(Node *&root) {
  if (!root) return;
  if (root->lazy == -1) return;
  root->lc->lazy = root->rc->lazy = root->lazy;
  for (int i = 0; i <= 5; i++) {
    root->lc->s[i] =
        (S[root->lc->r][i] - S[root->lc->l - 1][i] + MOD) * root->lazy % MOD;
    root->rc->s[i] =
        (S[root->rc->r][i] - S[root->rc->l - 1][i] + MOD) * root->lazy % MOD;
  }
  root->lazy = -1;
}
void update(Node *&root) {
  for (int i = 0; i <= 5; i++)
    root->s[i] = (root->lc->s[i] + root->rc->s[i]) % MOD;
}
void Build_Tree(Node *&root, int l, int r) {
  root = new Node;
  root->l = l;
  root->r = r;
  root->lazy = -1;
  root->lc = root->rc = 0;
  if (l == r) {
    root->s[0] = a[l];
    for (int i = 1; i <= 5; i++) root->s[i] = root->s[i - 1] * l % MOD;
    return;
  }
  int mid = (l + r) >> 1;
  Build_Tree(root->lc, l, mid);
  Build_Tree(root->rc, mid + 1, r);
  update(root);
}
void Modify(Node *&root, int l, int r, long long x) {
  if (!root) return;
  if (root->l > r || root->r < l) return;
  if (root->l >= l && root->r <= r) {
    root->lazy = x;
    for (int i = 0; i <= 5; i++)
      root->s[i] = (S[root->r][i] - S[root->l - 1][i] + MOD) * x % MOD;
    return;
  }
  down(root);
  Modify(root->lc, l, r, x);
  Modify(root->rc, l, r, x);
  update(root);
}
long long Query(Node *root, int l, int r, int k) {
  if (!root) return 0;
  if (root->l > r || root->r < l) return 0;
  if (root->l >= l && root->r <= r) {
    long long x = 1, ret = 0;
    for (int i = 0; i <= k; i++) {
      ret += (i % 2 ? -1 : 1) * C[k][i] * (root->s[k - i] * x % MOD) % MOD;
      x = x * (l - 1) % MOD;
    }
    return (ret % MOD + MOD) % MOD;
  }
  down(root);
  return (Query(root->lc, l, r, k) + Query(root->rc, l, r, k)) % MOD;
}
void print(Node *root) {
  if (!root) return;
  cout << root->l << " " << root->r << "  :  ";
  for (int i = 0; i <= 5; i++) cout << root->s[i] << " ";
  cout << endl;
  print(root->lc);
  print(root->rc);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  Init();
  Build_Tree(tree, 1, n);
  for (int i = 1; i <= m; i++) {
    char op;
    int l, r;
    cin >> op >> l >> r;
    if (op == '?') {
      int k;
      cin >> k;
      cout << Query(tree, l, r, k) % MOD << endl;
    } else {
      long long x;
      cin >> x;
      Modify(tree, l, r, x);
    }
  }
  return 0;
}