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, m, l, r, ans, nowans, val, D, C[6][6];
int tree[100010 * 4][6], lazy[100010 * 4], a[100010], Pow[100010][6],
    SPow[6][100010];
inline void up(int k) {
  for (int d = 0; d <= 5; d++) {
    tree[k][d] = tree[k << 1][d] + tree[k << 1 | 1][d];
    if (tree[k][d] >= 1000000007) tree[k][d] -= 1000000007;
  }
}
void build(int k, int l, int r) {
  if (l == r) {
    tree[k][0] = a[l];
    for (int d = 1; d <= 5; d++)
      tree[k][d] = 1ll * tree[k][d - 1] * l % 1000000007;
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  up(k);
}
inline void down(int k, int l, int r) {
  if (lazy[k] == -1) return;
  lazy[k << 1] = lazy[k << 1 | 1] = lazy[k];
  int mid = (l + r) >> 1;
  for (int d = 0; d <= 5; d++) {
    tree[k << 1][d] = SPow[d][mid] - SPow[d][l - 1] + 1000000007;
    if (tree[k << 1][d] >= 1000000007) tree[k << 1][d] -= 1000000007;
    tree[k << 1][d] = 1ll * tree[k << 1][d] * lazy[k] % 1000000007;
    tree[k << 1 | 1][d] = SPow[d][r] - SPow[d][mid] + 1000000007;
    if (tree[k << 1 | 1][d] >= 1000000007) tree[k << 1 | 1][d] -= 1000000007;
    tree[k << 1 | 1][d] = 1ll * tree[k << 1 | 1][d] * lazy[k] % 1000000007;
  }
  lazy[k] = -1;
}
void modify(int k, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    lazy[k] = val;
    for (int d = 0; d <= 5; d++) {
      tree[k][d] = SPow[d][r] - SPow[d][l - 1] + 1000000007;
      if (tree[k][d] >= 1000000007) tree[k][d] -= 1000000007;
      tree[k][d] = 1ll * tree[k][d] * val % 1000000007;
    }
    return;
  }
  int mid = (l + r) >> 1;
  down(k, l, r);
  if (mid >= ll) modify(k << 1, l, mid, ll, rr);
  if (mid < rr) modify(k << 1 | 1, mid + 1, r, ll, rr);
  up(k);
}
void ask(int k, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    nowans += tree[k][D];
    if (nowans >= 1000000007) nowans -= 1000000007;
    return;
  }
  int mid = (l + r) >> 1;
  down(k, l, r);
  if (mid >= ll) ask(k << 1, l, mid, ll, rr);
  if (mid < rr) ask(k << 1 | 1, mid + 1, r, ll, rr);
}
int main() {
  memset(lazy, -1, sizeof(lazy));
  C[0][0] = 1;
  for (int i = 1; i <= 5; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    Pow[i][0] = 1;
    for (int d = 1; d <= 5; d++)
      Pow[i][d] = 1ll * Pow[i][d - 1] * i % 1000000007;
  }
  for (int d = 0; d <= 5; d++)
    for (int i = 1; i <= n; i++) {
      SPow[d][i] = SPow[d][i - 1] + Pow[i][d];
      if (SPow[d][i] >= 1000000007) SPow[d][i] -= 1000000007;
    }
  Pow[0][0] = 1;
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    char ch = getchar();
    while (ch != '?' && ch != '=') ch = getchar();
    scanf("%d%d%d", &l, &r, &val);
    if (ch == '=') modify(1, 1, n, l, r);
    if (ch == '?') {
      ans = 0;
      for (int d = 0; d <= val; d++) {
        D = d;
        nowans = 0;
        ask(1, 1, n, l, r);
        nowans = 1ll * nowans * Pow[l - 1][val - d] % 1000000007 * C[val][d] %
                 1000000007;
        if ((val - d) & 1) nowans = -nowans + 1000000007;
        if (nowans >= 1000000007) nowans -= 1000000007;
        ans += nowans;
        if (ans >= 1000000007) ans -= 1000000007;
      }
      printf("%d\n", ans);
    }
  }
}