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>
inline void read(int &x) { scanf("%d", &x); }
inline void read(long long &x) { scanf("%I64d", &x); }
inline void read(double &x) { scanf("%lf", &x); }
inline void read(long double &x) {
  double tmp;
  read(tmp);
  x = tmp;
}
template <class T>
inline void read(T *a, int n) {
  for (int i = (0); i < (n); ++i) read(a[i]);
}
inline void write(int x) { printf("%d", x); }
inline void write(long long x) { printf("%I64d", x); }
inline void write(double x) { printf("%.10lf", x); }
inline void write(long double x) { printf("%.10lf", (double)x); }
template <class T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
template <class T>
inline void writeln(T *a, int n) {
  for (int i = (0); i < (n); ++i) {
    write(a[i]);
    putchar(' ');
  }
  putchar('\n');
}
template <class T>
inline void writelnln(T *a, int n) {
  for (int i = (0); i < (n); ++i) writeln(a[i]);
}
const int MOD = 1000000007;
const long long MODLL = 1000000007LL;
inline long long pow(long long x, int y) {
  long long ans = 1;
  for (int i = (30); i >= (0); --i) {
    ans = ans * ans % MODLL;
    if (y & (1 << i)) ans = ans * x % MODLL;
  }
  return ans;
}
inline long long inv(long long x) { return pow(x, MOD - 2); }
const long long inv2 = inv(2);
const long long inv4 = inv(4);
const long long inv6 = inv(6);
const long long inv12 = inv(12);
const long long inv30 = inv(30);
struct data {
  long long sum[6];
  inline data(long long x = 0) {
    for (int i = (0); i < (6); ++i) sum[i] = x;
  }
};
inline data merge(data a, long long siz, data b) {
  data c;
  c.sum[0] = (a.sum[0] + b.sum[0]) % MODLL;
  c.sum[1] = (a.sum[1] + b.sum[1] + siz * b.sum[0]) % MODLL;
  long long siz2 = siz * siz % MODLL;
  c.sum[2] =
      (a.sum[2] + b.sum[2] + siz2 * b.sum[0] + 2LL * siz * b.sum[1]) % MODLL;
  long long siz3 = siz2 * siz % MODLL;
  c.sum[3] = (a.sum[3] + b.sum[3] + siz3 * b.sum[0] +
              3LL * siz2 % MODLL * b.sum[1] + 3LL * siz % MODLL * b.sum[2]) %
             MODLL;
  long long siz4 = siz3 * siz % MODLL;
  c.sum[4] =
      (a.sum[4] + b.sum[4] + siz4 * b.sum[0] + 4LL * siz3 % MODLL * b.sum[1] +
       6LL * siz2 % MODLL * b.sum[2] + 4LL * siz % MODLL * b.sum[3]) %
      MODLL;
  long long siz5 = siz4 * siz % MODLL;
  c.sum[5] = (a.sum[5] + b.sum[5] + siz5 * b.sum[0] +
              5LL * siz4 % MODLL * b.sum[1] + 10LL * siz3 % MODLL * b.sum[2] +
              10LL * siz2 % MODLL * b.sum[3] + 5LL * siz % MODLL * b.sum[4]) %
             MODLL;
  return c;
}
inline data make(long long x, long long n) {
  data ans;
  ans.sum[0] = n * x % MODLL;
  ans.sum[1] = n * (n + 1LL) % MODLL * inv2 % MODLL * x % MODLL;
  ans.sum[2] = n * (n + 1LL) % MODLL * (2LL * n + 1LL) % MODLL * inv6 % MODLL *
               x % MODLL;
  ans.sum[3] = n * n % MODLL * (n + 1LL) % MODLL * (n + 1LL) % MODLL * inv4 %
               MODLL * x % MODLL;
  ans.sum[4] = n * (n + 1LL) % MODLL * (2LL * n + 1LL) % MODLL *
               (3LL * n * n + 3LL * n - 1LL) % MODLL * inv30 % MODLL * x %
               MODLL;
  ans.sum[5] = n * n % MODLL * (n + 1LL) % MODLL * (n + 1LL) % MODLL *
               (2LL * n * n + 2LL * n - 1LL) % MODLL * inv12 % MODLL * x %
               MODLL;
  return ans;
}
struct node {
  node *ls, *rs;
  int l, r, m, mark, size;
  data sum;
  inline void upd() { sum = merge(ls->sum, m + 1 - l, rs->sum); }
  inline node(int ll, int rr)
      : l(ll), r(rr), m((ll + rr) >> 1), mark(-1), size(rr - ll + 1) {
    if (l == r) {
      ls = rs = NULL;
      long long tmp;
      read(tmp);
      sum = data(tmp);
    } else {
      ls = new node(l, m);
      rs = new node(m + 1, r);
      upd();
    }
  }
  inline void add(int x) {
    mark = x;
    sum = make(x, size);
  }
  inline void push() {
    if (mark != -1) {
      if (ls) {
        ls->add(mark);
        rs->add(mark);
      }
      mark = -1;
    }
  }
  inline void chg(int ll, int rr, int x) {
    if (l == ll && r == rr)
      add(x);
    else {
      push();
      if (rr <= m)
        ls->chg(ll, rr, x);
      else if (ll > m)
        rs->chg(ll, rr, x);
      else {
        ls->chg(ll, m, x);
        rs->chg(m + 1, rr, x);
      }
      upd();
    }
  }
  inline data gsum(int ll, int rr) {
    if (l == ll && r == rr) return sum;
    push();
    if (rr <= m)
      return ls->gsum(ll, rr);
    else if (ll > m)
      return rs->gsum(ll, rr);
    else {
      data ld = ls->gsum(ll, m), rd = rs->gsum(m + 1, rr);
      return merge(ld, m + 1 - ll, rd);
    }
  }
};
int main() {
  int n, m;
  read(n);
  read(m);
  node *root = new node(1, n);
  while (m--) {
    char op[4];
    int l, r, x;
    scanf("%s%d%d%d", op, &l, &r, &x);
    if (op[0] == '=')
      root->chg(l, r, x);
    else
      writeln(root->gsum(l, r).sum[x]);
  }
  return 0;
}