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;
long long MOD = 1000000007;
long long sum[100001][6];
long long del[100001][6][6];
long long choose[6][6];
int aa[100001];
struct node {
  long long A[6];
  int sz;
  int carry;
  void update(long long val) {
    for (int k = 0; k < (6); ++k) {
      A[k] = val * sum[sz][k] % MOD;
    }
    carry = val;
    return;
  }
  long long calc(long long delta, int k) {
    assert(k < 6 and k >= 0);
    long long ans = 0;
    for (int i = 0; i <= k; ++i) {
      ans += A[k - i] * del[delta][k][i] % MOD;
    }
    return ans % MOD;
  }
  void merge(node& l, node& r) {
    for (int k = 0; k < (6); ++k) {
      A[k] = l.A[k] + r.calc(l.sz, k);
      if (A[k] >= MOD) A[k] -= MOD;
    }
    sz = l.sz + r.sz;
    carry = -1;
  }
  void split(node& l, node& r) {
    if (carry != -1) {
      l.carry = r.carry = carry;
      l.update(carry);
      r.update(carry);
      carry = -1;
    }
  }
  void print() {
    printf("sz = %d, carry = %d :: ", sz, carry);
    for (int i = 0; i < (6); ++i) cout << A[i] << " ";
  }
} tree[1 << 18];
void init(int root, int l, int r) {
  if (l == r) {
    tree[root].sz = 1;
    tree[root].carry = -1;
    return tree[root].update(aa[l]);
  }
  int left = 2 * root, right = left + 1, m = (l + r) / 2;
  init(left, l, m);
  init(right, m + 1, r);
  tree[root].merge(tree[left], tree[right]);
  return;
}
void update(int root, int l, int r, int i, int j, int x) {
  if (i <= l and r <= j) return tree[root].update(x);
  int left = root * 2, right = left + 1, m = (l + r) / 2;
  tree[root].split(tree[left], tree[right]);
  if (i <= m) update(left, l, m, i, j, x);
  if (m + 1 <= j) update(right, m + 1, r, i, j, x);
  tree[root].merge(tree[left], tree[right]);
}
long long query(int root, int l, int r, int i, int j, int k) {
  if (i <= l and r <= j) return tree[root].calc(l - i, k);
  int left = root * 2, right = left + 1, m = (l + r) / 2;
  tree[root].split(tree[left], tree[right]);
  long long ans = 0;
  if (i <= m) ans += query(left, l, m, i, j, k);
  if (m + 1 <= j) ans += query(right, m + 1, r, i, j, k);
  return ans % MOD;
}
void print() {
  for (int i = 1; i < 8; ++i) {
    printf("Node %d :- ", i);
    tree[i].print();
    putchar(10);
  }
}
int main() {
  memset(choose, 0, sizeof(choose));
  choose[0][0] = 1;
  for (int i = 1; i < 6; ++i)
    for (int j = 0; j <= i; ++j) {
      if (j == 0 || j == i)
        choose[i][j] = 1;
      else
        choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
    }
  for (int k = 0; k < (6); ++k) sum[0][k] = 0;
  for (long long i = 1; i <= 100000; ++i) {
    sum[i][0] = 1;
    for (int k = 1; k < 6; ++k) {
      sum[i][k] = sum[i][k - 1] * i % MOD;
    }
    for (int k = 0; k < 6; ++k)
      for (int kk = 0; kk <= k; ++kk) {
        del[i][k][kk] = sum[i][kk] * choose[k][kk] % MOD;
      }
    for (int k = 0; k < (6); ++k) sum[i][k] = (sum[i - 1][k] + sum[i][k]) % MOD;
  }
  for (int k = 0; k < (6); ++k)
    for (int kk = 0; kk < (k + 1); ++kk) {
      del[0][k][kk] = (kk == 0);
    }
  int n, m, l, r, x;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (n); ++i) {
    scanf("%d", aa + i + 1);
  }
  init(1, 1, n);
  char str[2];
  while (m--) {
    scanf("%s %d %d %d", str, &l, &r, &x);
    if (str[0] == '?') {
      printf("%lld\n", query(1, 1, n, l, r, x));
    } else {
      update(1, 1, n, l, r, x);
    }
  }
  return 0;
}