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 long long MOD = 1e9 + 7;
struct poly {
  valarray<long long> coffs;
  poly(int degree) : coffs(degree + 1) {}
  int degree() const { return coffs.size() - 1; }
  poly operator*(const poly &a) const {
    poly res(a.degree() + degree());
    for (int i = 0; i < coffs.size(); i++) {
      for (int j = 0; j <= a.degree(); j++) {
        res.coffs[i + j] += coffs[i] * a.coffs[j] % MOD;
        res.coffs[i + j] %= MOD;
      }
    }
    return res;
  }
  poly operator^(int p) {
    poly res(0);
    res.coffs[0] = 1;
    poly tmp = *this;
    for (; p; p >>= 1) {
      if (p & 1) res = res * tmp;
      tmp = tmp * tmp;
    }
    return res;
  }
};
long long fast_power(long long base, int p) {
  long long res = 1;
  for (; p; p >>= 1) {
    if (p & 1) res = res * base % MOD;
    base = base * base % MOD;
  }
  return res;
}
long long dp[100009][7];
long long sum_of_pows(int n, int k) {
  if (n == 0) return 0;
  long long &ret = dp[n][k];
  if (ret != -1) return ret;
  return ret = (sum_of_pows(n - 1, k) + fast_power(n, k)) % MOD;
}
struct Node {
  valarray<long long> vals;
  long long lazy;
  Node() : vals(6), lazy(-1) {}
  void setValue(long long v, int ns, int ne) {
    lazy = v;
    for (int i = 0; i < 6; i++) {
      vals[i] =
          (sum_of_pows(ne, i) - sum_of_pows(ns - 1, i) + MOD) % MOD * v % MOD;
    }
  }
} Nodes[1 << 18];
int qs, qe;
long long value;
int n;
void update(int ni = 0, int ns = 1, int ne = n) {
  if (ns > qe || ne < qs) return;
  Node &nd = Nodes[ni];
  if (ns >= qs && ne <= qe) {
    nd.setValue(value, ns, ne);
    return;
  }
  int mid = (ns + ((ne - ns) >> 1));
  int left = (ni << 1) + 1, right = left + 1;
  if (nd.lazy != -1) {
    Nodes[left].setValue(nd.lazy, ns, mid);
    Nodes[right].setValue(nd.lazy, mid + 1, ne);
    nd.lazy = -1;
  }
  update(left, ns, mid);
  update(right, mid + 1, ne);
  nd.vals = (Nodes[left].vals + Nodes[right].vals) % MOD;
}
valarray<long long> query(int ni = 0, int ns = 1, int ne = n) {
  if (ns > qe || ne < qs) return valarray<long long>(6);
  Node &nd = Nodes[ni];
  if (ns >= qs && ne <= qe) {
    return nd.vals;
  }
  int mid = (ns + ((ne - ns) >> 1));
  int left = (ni << 1) + 1, right = left + 1;
  if (nd.lazy != -1) {
    Nodes[left].setValue(nd.lazy, ns, mid);
    Nodes[right].setValue(nd.lazy, mid + 1, ne);
    nd.lazy = -1;
  }
  return (query(left, ns, mid) + query(right, mid + 1, ne)) % MOD;
}
int main() {
  ios::sync_with_stdio(false);
  memset(dp, -1, sizeof dp);
  int c, q;
  cin >> n >> q;
  for (c = 0; c < n; c++) {
    cin >> value;
    qs = qe = c + 1;
    update();
  }
  char a;
  while (q--) {
    cin >> a;
    cin >> qs >> qe >> value;
    if (a == '=')
      update();
    else {
      poly tmp(1);
      tmp.coffs[0] = (1 - (qs) + MOD) % MOD;
      tmp.coffs[1] = 1;
      tmp = tmp ^ value;
      valarray<long long> v = query()[slice(0, tmp.coffs.size(), 1)];
      cout << (tmp.coffs * v % MOD).sum() % MOD << endl;
    }
  }
  if (n == 0) return 0;
  return 0;
}