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;
int n, q, x, y, k;
int S[7][100005 * 4], lazy[7][100005 * 4], pre[7][100005];
int C[10][10];
char c;
int power(int x, int p, int bas, int son) {
  return 1ll * x * (pre[p][son] - pre[p][bas - 1] + 1000000007) % 1000000007;
}
void push(int node, int bas, int son, int po) {
  if (~lazy[po][node] && bas != son) {
    lazy[po][node * 2] = lazy[po][node * 2 + 1] = lazy[po][node];
    S[po][node * 2] = power(lazy[po][node], po, bas, ((bas + son) / 2));
    S[po][node * 2 + 1] = power(lazy[po][node], po, ((bas + son) / 2) + 1, son);
  }
  lazy[po][node] = -1;
}
int get(int node, int bas, int son, int x, int y, int po) {
  if (bas > y || son < x) return 0;
  if (bas >= x && son <= y) return S[po][node];
  push(node, bas, son, po);
  return (get(node * 2, bas, ((bas + son) / 2), x, y, po) +
          get(node * 2 + 1, ((bas + son) / 2) + 1, son, x, y, po)) %
         1000000007;
}
void up(int node, int bas, int son, int x, int y, int val, int po) {
  if (bas > y || son < x) return;
  if (bas >= x && son <= y) {
    S[po][node] = power(val, po, bas, son);
    lazy[po][node] = val;
    return;
  }
  push(node, bas, son, po);
  up(node * 2, bas, ((bas + son) / 2), x, y, val, po);
  up(node * 2 + 1, ((bas + son) / 2) + 1, son, x, y, val, po);
  S[po][node] = (S[po][node * 2] + S[po][node * 2 + 1]) % 1000000007;
}
void solve(int x, int y, int k) {
  int val = -x + 1;
  int now = 1;
  int res = 0;
  for (int i = k; i >= 0; i--) {
    res = (1ll * res +
           1ll * get(1, 1, n, x, y, i) * now % 1000000007 * C[k][k - i] %
               1000000007 +
           3ll * 1000000007) %
          1000000007;
    now = 1ll * now * val % 1000000007;
  }
  printf("%d\n", res);
}
int main() {
  for (int i = 0; i <= 5; i++) memset(lazy[i], -1, sizeof(lazy[i]));
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    for (int p = 0, now = 1; p <= 5; p++, now = 1ll * now * i % 1000000007) {
      pre[p][i] = (pre[p][i - 1] + now) % 1000000007;
    }
  }
  C[0][0] = 1;
  for (int i = 1; i <= 6; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    for (int j = 0; j <= 5; j++) {
      up(1, 1, n, i, i, x, j);
    }
  }
  while (q--) {
    scanf(" %c %d %d %d", &c, &x, &y, &k);
    if (c == '?') {
      solve(x, y, k);
    } else {
      for (int i = 0; i <= 5; i++) {
        up(1, 1, n, x, y, k, i);
      }
    }
  }
}