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 = 1e9 + 7;
int n, q;
int C[6][6];
vector<int> A;
int Add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
int Sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
int Mul(int x, int y) {
  if (x < 0) {
    x += mod;
  }
  if (y < 0) {
    y += mod;
  }
  return 1ll * x * y % mod;
}
struct SegTree {
  int n;
  vector<int> Psum;
  vector<int> Tree, Lazy;
  void Init(vector<int> &A, int k) {
    n = A.size() - 1;
    Psum.resize(n + 1);
    Tree.resize(4 * n + 5);
    Lazy.resize(4 * n + 5);
    for (int i = 1; i <= n; i++) {
      int cur = 1;
      for (int j = 0; j < k; j++) {
        cur = Mul(cur, i);
      }
      Psum[i] = Add(Psum[i - 1], cur);
    }
    Build(1, 1, n, A);
  }
  void Build(int node, int l, int r, vector<int> &A) {
    Lazy[node] = mod;
    if (l == r) {
      Tree[node] = Mul(A[l], Sub(Psum[r], Psum[l - 1]));
      return;
    }
    int mid = (l + r) >> 1;
    Build(node << 1, l, mid, A);
    Build(node << 1 | 1, mid + 1, r, A);
    Tree[node] = Add(Tree[node << 1], Tree[node << 1 | 1]);
  }
  void Push(int node, int l, int r) {
    if (Lazy[node] != mod) {
      if (l != r) {
        Lazy[node << 1] = Lazy[node << 1 | 1] = Lazy[node];
      }
      Tree[node] = Mul(Lazy[node], Sub(Psum[r], Psum[l - 1]));
      Lazy[node] = mod;
    }
  }
  void Update(int node, int l, int r, int L, int R, int val) {
    Push(node, l, r);
    if (l > R or r < L) {
      return;
    }
    if (L <= l and r <= R) {
      Lazy[node] = val;
      Push(node, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    Update(node << 1, l, mid, L, R, val);
    Update(node << 1 | 1, mid + 1, r, L, R, val);
    Tree[node] = Add(Tree[node << 1], Tree[node << 1 | 1]);
  }
  int Get(int node, int l, int r, int L, int R) {
    Push(node, l, r);
    if (l > R or r < L) {
      return 0;
    }
    if (L <= l and r <= R) {
      return Tree[node];
    }
    int mid = (l + r) >> 1;
    return Add(Get(node << 1, l, mid, L, R),
               Get(node << 1 | 1, mid + 1, r, L, R));
  }
} IT[6];
int main() {
  cin >> n >> q;
  A.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < 6; i++) {
    C[0][i] = 1;
    for (int j = 1; j <= i; j++) {
      C[j][i] = C[j - 1][i - 1] + C[j][i - 1];
    }
    IT[i].Init(A, i);
  }
  while (q--) {
    char quest;
    cin >> quest;
    if (quest == '?') {
      int l, r, k;
      cin >> l >> r >> k;
      int ans = 0;
      int tmp = Sub(1, l), cur = 1;
      for (int i = k; i >= 0; i--) {
        ans = Add(ans, Mul(C[i][k], Mul(cur, IT[i].Get(1, 1, n, l, r))));
        cur = Mul(cur, tmp);
      }
      cout << ans << '\n';
    } else {
      int l, r, x;
      cin >> l >> r >> x;
      for (int i = 0; i <= 5; i++) {
        IT[i].Update(1, 1, n, l, r, x);
      }
    }
  }
}