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 = 1000000007;
int C[6][6], a[100005];
int Mod(int x) { return x < mod ? x : x - mod; }
int S[6][100005];
int d[400005], ret[400005][6];
void Update(int k, int t, int l, int r) {
  d[k] = t;
  for (int i = 0; i < 6; i++)
    ret[k][i] = ((long long)S[i][r] - S[i][l - 1] + mod) * t % mod;
}
void Pushdown(int k, int l, int m, int r) {
  if (d[k] > -1)
    Update(k * 2, d[k], l, m), Update(k * 2 + 1, d[k], m + 1, r), d[k] = -1;
}
void Change(int k, int l, int r, int x, int y, int t) {
  if (l == x && r == y) {
    Update(k, t, l, r);
    return;
  }
  int m = l + r >> 1;
  Pushdown(k, l, m, r);
  if (y <= m)
    Change(k * 2, l, m, x, y, t);
  else if (x > m)
    Change(k * 2 + 1, m + 1, r, x, y, t);
  else
    Change(k * 2, l, m, x, m, t), Change(k * 2 + 1, m + 1, r, m + 1, y, t);
  for (int i = 0; i < 6; i++)
    ret[k][i] = Mod(ret[k * 2][i] + ret[k * 2 + 1][i]);
}
int Query(int k, int l, int r, int x, int y, int t) {
  if (l == x && r == y) return ret[k][t];
  int m = l + r >> 1;
  Pushdown(k, l, m, r);
  if (y <= m) return Query(k * 2, l, m, x, y, t);
  if (x > m) return Query(k * 2 + 1, m + 1, r, x, y, t);
  return Mod(Query(k * 2, l, m, x, m, t) +
             Query(k * 2 + 1, m + 1, r, m + 1, y, t));
}
int main() {
  int n, m;
  memset(d, -1, sizeof(d));
  for (int i = 0; i < 6; i++)
    for (int j = C[i][0] = 1; j <= i; j++)
      C[i][j] = Mod(C[i - 1][j] + mod - C[i - 1][j - 1]);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) S[0][i] = i;
  for (int i = 1; i < 6; i++)
    for (int j = 1; j <= n; j++)
      S[i][j] =
          (S[i][j - 1] + ((long long)S[i - 1][j] - S[i - 1][j - 1] + mod) * j) %
          mod;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Change(1, 1, n, i, i, a[i]);
  char s[10];
  for (int l, r, d; m--;) {
    scanf("%s%d%d%d", s, &l, &r, &d);
    if (s[0] == '=')
      Change(1, 1, n, l, r, d);
    else {
      int ans = 0;
      for (int i = 0, t = 1; i <= d; i++, t = (long long)t * (l - 1) % mod)
        ans = (ans + (long long)Query(1, 1, n, l, r, d - i) * t % mod *
                         C[d][i] % mod) %
              mod;
      printf("%d\n", ans);
    }
  }
}