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 MAX = 100010;
const int MOD = 1E9 + 7;
struct dtree {
  int sumk[6], mem;
  dtree() {
    memset(sumk, 0, sizeof(sumk));
    mem = -1;
  }
};
dtree s[MAX * 4];
int dsum[6][MAX];
void push(int tree_ind, int tree_l, int tree_r) {
  if (s[tree_ind].mem == -1) return;
  s[tree_ind].sumk[0] = (1LL * s[tree_ind].mem * (tree_r - tree_l + 1)) % MOD;
  for (int i = 1; i < 6; ++i)
    s[tree_ind].sumk[i] =
        (MOD + 1ll * s[tree_ind].mem *
                   (MOD + dsum[i][tree_r] - dsum[i][tree_l - 1])) %
        MOD;
  if (tree_l != tree_r)
    s[tree_ind * 2].mem = s[tree_ind * 2 + 1].mem = s[tree_ind].mem;
  s[tree_ind].mem = -1;
}
void set_val(int tree_ind, int tree_l, int tree_r, int l, int r, int x) {
  if (tree_l > r || tree_r < l) return;
  push(tree_ind, tree_l, tree_r);
  if (tree_l >= l && tree_r <= r)
    s[tree_ind].mem = x;
  else {
    int mid = (tree_l + tree_r) / 2;
    set_val(tree_ind * 2, tree_l, mid, l, r, x);
    push(tree_ind * 2, tree_l, mid);
    set_val(tree_ind * 2 + 1, mid + 1, tree_r, l, r, x);
    push(tree_ind * 2 + 1, mid + 1, tree_r);
    for (int i = 0; i < 6; ++i)
      s[tree_ind].sumk[i] =
          (s[tree_ind * 2].sumk[i] + s[tree_ind * 2 + 1].sumk[i]) % MOD;
  }
}
long long prod(long long a, long long b, int p = 1) {
  long long res = a;
  for (int i = 0; i < p; ++i) res = (res * b) % MOD;
  return res;
}
int calc(int tree_ind, int tree_l, int tree_r, int l, int r, int k) {
  if (tree_l > r || tree_r < l) return 0;
  push(tree_ind, tree_l, tree_r);
  int z = (MOD + 1 - l) % MOD;
  if (tree_l >= l && tree_r <= r) switch (k) {
      case 0:
        return s[tree_ind].sumk[0];
      case 1:
        return (s[tree_ind].sumk[1] + 1 * prod(s[tree_ind].sumk[0], z)) % MOD;
      case 2:
        return (s[tree_ind].sumk[2] + 2 * prod(s[tree_ind].sumk[1], z) +
                1 * prod(s[tree_ind].sumk[0], z, 2)) %
               MOD;
      case 3:
        return (s[tree_ind].sumk[3] + 3 * prod(s[tree_ind].sumk[2], z) +
                3 * prod(s[tree_ind].sumk[1], z, 2) +
                1 * prod(s[tree_ind].sumk[0], z, 3)) %
               MOD;
      case 4:
        return (s[tree_ind].sumk[4] + 4 * prod(s[tree_ind].sumk[3], z) +
                6 * prod(s[tree_ind].sumk[2], z, 2) +
                4 * prod(s[tree_ind].sumk[1], z, 3) +
                1 * prod(s[tree_ind].sumk[0], z, 4)) %
               MOD;
      case 5:
        return (s[tree_ind].sumk[5] + 5 * prod(s[tree_ind].sumk[4], z) +
                10 * prod(s[tree_ind].sumk[3], z, 2) +
                10 * prod(s[tree_ind].sumk[2], z, 3) +
                5 * prod(s[tree_ind].sumk[1], z, 4) +
                1 * prod(s[tree_ind].sumk[0], z, 5)) %
               MOD;
    }
  int mid = (tree_l + tree_r) / 2;
  return (calc(tree_ind * 2, tree_l, mid, l, r, k) +
          calc(tree_ind * 2 + 1, mid + 1, tree_r, l, r, k)) %
         MOD;
}
bool solve() {
  for (int i = 1; i < MAX; ++i) {
    int p = 1;
    for (int k = 0; k < 6; ++k) {
      dsum[k][i] = (dsum[k][i - 1] + p) % MOD;
      p = (1LL * p * i) % MOD;
    }
  }
  int n, m;
  if (scanf("%d%d", &n, &m) == EOF) return false;
  for (int i = 0; i < n; ++i) {
    int a;
    scanf("%d", &a);
    set_val(1, 1, n, i + 1, i + 1, a);
  }
  for (int i = 0; i < m; ++i) {
    char s[10];
    int l, r, x;
    scanf("%s%d%d%d", s, &l, &r, &x);
    if (s[0] == '?')
      printf("%d\n", calc(1, 1, n, l, r, x));
    else
      set_val(1, 1, n, l, r, x);
  }
  return true;
}
int main() { solve(); }