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 tree[400005][6], arr[100005], lazy[400005];
int powers[100005][6];
void build(int i, int L, int R) {
  if (L == R) {
    tree[i][0] = arr[L];
    for (int j = 1; j <= 5; j++)
      tree[i][j] = (tree[i][j - 1] * 1LL * (L + 1)) % 1000000007;
    lazy[i] = -1;
    return;
  }
  build(i * 2 + 1, L, (L + R) / 2);
  build(i * 2 + 2, (L + R) / 2 + 1, R);
  for (int j = 0; j <= 5; j++)
    tree[i][j] = (tree[i * 2 + 1][j] + tree[i * 2 + 2][j]) % 1000000007;
  lazy[i] = -1;
}
void update(int i, int L, int R, int x, int y, int val) {
  if (lazy[i] != -1) {
    for (int j = 0; j <= 5; j++) {
      int temp = powers[R][j] - powers[L - 1][j];
      temp %= 1000000007;
      temp += 1000000007;
      temp %= 1000000007;
      tree[i][j] = (lazy[i] * 1LL * temp) % 1000000007;
    }
    if (L != R) {
      lazy[i * 2 + 1] = lazy[i];
      lazy[i * 2 + 2] = lazy[i];
    }
    lazy[i] = -1;
  }
  if (L >= x && R <= y) {
    lazy[i] = val;
    for (int j = 0; j <= 5; j++) {
      int temp = powers[R][j] - powers[L - 1][j];
      temp %= 1000000007;
      temp += 1000000007;
      temp %= 1000000007;
      tree[i][j] = (lazy[i] * 1LL * temp) % 1000000007;
    }
    if (L != R) {
      lazy[i * 2 + 1] = lazy[i];
      lazy[i * 2 + 2] = lazy[i];
    }
    lazy[i] = -1;
    return;
  }
  if (L > y || R < x) return;
  update(i * 2 + 1, L, (L + R) / 2, x, y, val);
  update(i * 2 + 2, (L + R) / 2 + 1, R, x, y, val);
  for (int j = 0; j <= 5; j++)
    tree[i][j] = (tree[i * 2 + 1][j] + tree[i * 2 + 2][j]) % 1000000007;
}
int query(int i, int L, int R, int x, int y, int k) {
  if (lazy[i] != -1) {
    for (int j = 0; j <= 5; j++) {
      int temp = powers[R][j] - powers[L - 1][j];
      temp %= 1000000007;
      temp += 1000000007;
      temp %= 1000000007;
      tree[i][j] = (lazy[i] * 1LL * temp) % 1000000007;
    }
    if (L != R) {
      lazy[i * 2 + 1] = lazy[i];
      lazy[i * 2 + 2] = lazy[i];
    }
    lazy[i] = -1;
  }
  if (L >= x && R <= y) return tree[i][k];
  if (L > y || R < x) return 0;
  return (query(i * 2 + 1, L, (L + R) / 2, x, y, k) +
          query(i * 2 + 2, (L + R) / 2 + 1, R, x, y, k)) %
         1000000007;
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  for (int i = 0; i <= 6; i++) powers[0][i] = 1;
  for (int i = 2; i <= n + 1; i++) {
    int tmp = 1;
    powers[i - 1][0] = (powers[i - 2][0] + tmp) % 1000000007;
    tmp = (tmp * 1LL * i) % 1000000007;
    powers[i - 1][1] = (powers[i - 2][1] + tmp) % 1000000007;
    tmp = (tmp * 1LL * i) % 1000000007;
    powers[i - 1][2] = (powers[i - 2][2] + tmp) % 1000000007;
    tmp = (tmp * 1LL * i) % 1000000007;
    powers[i - 1][3] = (powers[i - 2][3] + tmp) % 1000000007;
    tmp = (tmp * 1LL * i) % 1000000007;
    powers[i - 1][4] = (powers[i - 2][4] + tmp) % 1000000007;
    tmp = (tmp * 1LL * i) % 1000000007;
    powers[i - 1][5] = (powers[i - 2][5] + tmp) % 1000000007;
  }
  build(0, 1, n);
  string in;
  int x, y, z;
  while (m--) {
    cin >> in >> x >> y >> z;
    if (in == "=")
      update(0, 1, n, x, y, z);
    else {
      long long res, pw = x, A, B, C, D, E, F;
      if (z == 0) {
        res = query(0, 1, n, x, y, 0);
      } else if (z == 1) {
        A = query(0, 1, n, x, y, 1);
        B = (query(0, 1, n, x, y, 0) * 1LL * pw) % 1000000007;
        res = (A - B) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
      } else if (z == 2) {
        A = query(0, 1, n, x, y, 2);
        B = (query(0, 1, n, x, y, 1) * 2LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        C = (query(0, 1, n, x, y, 0) * 1LL * pw) % 1000000007;
        res = (A - B + C) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
      } else if (z == 3) {
        A = query(0, 1, n, x, y, 3);
        B = (query(0, 1, n, x, y, 2) * 3LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        C = (query(0, 1, n, x, y, 1) * 3LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        D = (query(0, 1, n, x, y, 0) * 1LL * pw) % 1000000007;
        res = (A - B + C) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
        res = (res - D) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
      } else if (z == 4) {
        A = query(0, 1, n, x, y, 4);
        B = (query(0, 1, n, x, y, 3) * 4LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        C = (query(0, 1, n, x, y, 2) * 6LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        D = (query(0, 1, n, x, y, 1) * 4LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        E = (query(0, 1, n, x, y, 0) * 1LL * pw) % 1000000007;
        res = (A - B + C) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
        res = (res - D + E) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
      } else {
        A = query(0, 1, n, x, y, 5);
        B = (query(0, 1, n, x, y, 4) * 5LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        C = (query(0, 1, n, x, y, 3) * 1LL * pw) % 1000000007;
        C = (C * 10LL) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        D = (query(0, 1, n, x, y, 2) * 1LL * pw) % 1000000007;
        D = (D * 10LL) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        E = (query(0, 1, n, x, y, 1) * 5LL * pw) % 1000000007;
        pw = (x * 1LL * pw) % 1000000007;
        F = (query(0, 1, n, x, y, 0) * 1LL * pw) % 1000000007;
        res = (A - B + C) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
        res = (res - D + E) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
        res = (res - F) % 1000000007;
        res += 1000000007;
        res %= 1000000007;
      }
      cout << res << "\n";
    }
  }
  return 0;
}