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 Z = -3000000;
const int MOD = (int)1e9 + 7;
int YEY[100006][6];
int md(long long a) { return (int)(a % MOD); }
int sm(int a, int b) { return md((long long)a + b); }
int mm(int a, int b) { return md((long long)a * b); }
int im(int a, int b) {
  int ans = md(a) - md(b);
  if (ans < 0) ans += MOD;
  return ans;
}
int pm(int a, int k) {
  if (k == 0) return 1;
  if (k == 1)
    return a;
  else {
    int ans = mm(a, a);
    for (int i = 3; i <= k; ++i) ans = mm(ans, a);
    return ans;
  }
}
int E(int l, int r, int k) {
  if (l == 0) return YEY[r][k];
  return im(YEY[r][k], YEY[l - 1][k]);
}
class Node {
 public:
  int l, r, sum[6], color;
  Node* left;
  Node* right;
  Node(int L, int R, vector<int>& data) : l(L), r(R), color(Z) {
    if (l == r) {
      for (int i = 0; i < 6; ++i) sum[i] = mm(data[l], pm(l + 1, i));
      left = NULL;
      right = NULL;
    } else {
      int m = (l + r) / 2;
      left = new Node(l, m, data);
      right = new Node(m + 1, r, data);
      for (int i = 0; i < 6; ++i) sum[i] = sm(left->sum[i], right->sum[i]);
    }
  }
  int sumk(int L, int R, int k, int cl = Z) {
    if (L > R) return 0;
    int cl2 = cl == Z ? color : cl;
    if (cl2 != Z && L >= l && R <= r) {
      return mm(cl2, E(L + 1, R + 1, k));
    }
    int m = (l + r) / 2;
    if (L == l && R == r)
      return cl2 == Z ? sum[k] : mm(cl2, E(L + 1, R + 1, k));
    return sm(left->sumk(L, min(R, m), k, cl2),
              right->sumk(max(L, m + 1), R, k, cl2));
  }
  int SUM(int L, int R, int k) {
    if (k == 0) {
      int ans = sumk(L, R, 0);
      return ans;
    }
    if (k == 1) {
      int A0 = sumk(L, R, 0);
      int A1 = sumk(L, R, 1);
      int ans = im(A1, mm(L, A0));
      return ans;
    }
    if (k == 2) {
      int A0 = sumk(L, R, 0);
      int A1 = sumk(L, R, 1);
      int A2 = sumk(L, R, 2);
      int B1 = A2;
      int B2 = mm(A0, pm(L, 2));
      int C1 = mm(A1, mm(L, 2));
      int ans = im(sm(B1, B2), C1);
      return ans;
    }
    if (k == 3) {
      int A0 = sumk(L, R, 0);
      int A1 = sumk(L, R, 1);
      int A2 = sumk(L, R, 2);
      int A3 = sumk(L, R, 3);
      int B1 = A3;
      int B2 = mm(A1, mm(3, pm(L, 2)));
      int C1 = mm(A2, mm(3, L));
      int C2 = mm(A0, pm(L, 3));
      int ans = im(sm(B1, B2), sm(C1, C2));
      return ans;
    }
    if (k == 4) {
      int A0 = sumk(L, R, 0);
      int A1 = sumk(L, R, 1);
      int A2 = sumk(L, R, 2);
      int A3 = sumk(L, R, 3);
      int A4 = sumk(L, R, 4);
      int B1 = A4;
      int B2 = mm(A2, mm(6, pm(L, 2)));
      int B3 = mm(A0, pm(L, 4));
      int C1 = mm(A3, mm(4, L));
      int C2 = mm(A1, mm(4, pm(L, 3)));
      int ans = im(sm(sm(B1, B2), B3), (sm(C1, C2)));
      return ans;
    }
    if (k == 5) {
      int A0 = sumk(L, R, 0);
      int A1 = sumk(L, R, 1);
      int A2 = sumk(L, R, 2);
      int A3 = sumk(L, R, 3);
      int A4 = sumk(L, R, 4);
      int A5 = sumk(L, R, 5);
      int B1 = A5;
      int B2 = mm(A3, mm(10, pm(L, 2)));
      int B3 = mm(A1, mm(5, pm(L, 4)));
      int C1 = mm(A4, mm(5, L));
      int C2 = mm(A2, mm(10, pm(L, 3)));
      int C3 = mm(A0, pm(L, 5));
      int ans = im(sm(sm(B1, B2), B3), sm(sm(C1, C2), C3));
      return ans;
    }
    return 0;
  }
  void paint(int L, int R, int COLOR) {
    if (l > R || L > r || R < l) return;
    if (l == L && r == R) {
      color = COLOR;
    } else {
      if (color != Z && left && right) {
        left->color = color;
        right->color = color;
        color = Z;
      }
      int m = (l + r) / 2;
      left->paint(L, min(R, m), COLOR);
      right->paint(max(L, m + 1), R, COLOR);
      int sum1[6], sum2[6];
      if (left->color != Z) {
        for (int i = 0; i < 6; ++i)
          sum1[i] = mm(left->color, E(left->l + 1, left->r + 1, i));
      } else {
        for (int i = 0; i < 6; ++i) sum1[i] = left->sum[i];
      }
      if (right->color != Z) {
        for (int i = 0; i < 6; ++i)
          sum2[i] = mm(right->color, E(right->l + 1, right->r + 1, i));
      } else {
        for (int i = 0; i < 6; ++i) sum2[i] = right->sum[i];
      }
      for (int i = 0; i < 6; ++i) sum[i] = sm(sum1[i], sum2[i]);
    }
  }
  void print(int pow, string prefix = "") {
    cout << prefix << "Node " << l << ' ' << r << ' ' << sum[0] << ' '
         << sum[pow] << ' ' << color;
    if (left && right) {
      cout << "\n";
      left->print(pow, prefix + "    ");
      cout << "\n";
      right->print(pow, prefix + "    ");
      cout << "\n";
    }
  }
};
bool test(int N, Node& tree, int a[], int L, int R, int pow) {
  int S1 = tree.SUM(L, R, pow);
  int S2 = S1;
  return S1 == S2;
}
void tpaint(int N, Node& tree, int a[], int L, int R, int color) {
  tree.paint(L, R, color);
}
int main() {
  for (int i = 0; i < 6; ++i) YEY[0][i] = 0;
  for (int i = 1; i < 100006; ++i)
    for (int j = 0; j < 6; ++j) YEY[i][j] = sm(YEY[i - 1][j], pm(i, j));
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<int> s(n);
  for (int i = 0; i < n; ++i) cin >> s[i];
  Node tree(0, n - 1, s);
  char t;
  int l, r, xk;
  for (int i = 0; i < m; ++i) {
    cin >> t >> l >> r >> xk;
    if (t == '=')
      tree.paint(l - 1, r - 1, xk);
    else
      cout << tree.SUM(l - 1, r - 1, xk) << '\n';
  }
  return 0;
}