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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class MoreQueriesToArray {
    static int[][] tree = new int[4 * 111111][6];
    static long[] lazy = new long[4 * 111111];
    static long[][] sums = new long[6][4 * 111111];
    static int MOD = 1000000007;

    public static long[][] C(int MAX) {
        long C[][] = new long[MAX + 1][MAX + 1];
        for (int i = 0; i < C.length; i++)
            C[i][0] = 1;
        for (int i = 1; i < C.length; i++)
            C[0][i] = 0;
        for (int i = 1; i < C.length; i++)
            for (int j = 1; j < C[i].length; j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        return C;
    }

    public static long sum(int l, int r, int deg) {
        return ((sums[deg][r] - ((l > 0) ? sums[deg][l - 1] : 0)) % MOD + MOD)
                % MOD;
    }

    public static void push(int i, int l, int r) {
        if (lazy[i] != -1) {
            for (int j = 0; j < 6; j++)
                tree[i][j] = (int) ((sum(l, r, j) * lazy[i]) % MOD);
            if (i * 2 + 1 < tree.length)
                lazy[i * 2 + 1] = lazy[i];
            if (i * 2 + 2 < tree.length)
                lazy[i * 2 + 2] = lazy[i];
            lazy[i] = -1;
        }
    }

    public static int query(int i, int a, int b, int l, int r, int k) {
        push(i, a, b);
        if (a >= l && b <= r)
            return tree[i][k];
        else if (a > r || b < l)
            return 0;
        else
            return (query(i * 2 + 1, a, (a + b) / 2, l, r, k) + query(
                    i * 2 + 2, (a + b) / 2 + 1, b, l, r, k)) % MOD;
    }

    public static void update(int i, int a, int b, int l, int r, int x) {
        push(i, a, b);
        if (a >= l && b <= r) {
            lazy[i] = x;
            push(i, a, b);
        } else if (a > r || b < l)
            return;
        else {
            update(i * 2 + 1, a, (a + b) / 2, l, r, x);
            update(i * 2 + 2, (a + b) / 2 + 1, b, l, r, x);
            for (int j = 0; j < 6; j++)
                tree[i][j] = (int) ((tree[i * 2 + 1][j] + tree[i * 2 + 2][j]) % MOD);
        }
    }

    public static long modPow(long a, int b) {
        if (a == 0)
            return 0;
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = (res * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        for (int i = 0; i < 6; i++)
            for (int j = 0; j < 111111; j++) {
                sums[i][j] = (int) modPow(j + 1, i);
                if (j > 0)
                    sums[i][j] = (sums[i][j] + sums[i][j - 1]) % MOD;
            }
        Arrays.fill(lazy, -1);
        int n = in.nextInt();
        int m = in.nextInt();
        long[][] C = C(10);
        for (int i = 0; i < n; i++) {
            int ai = in.nextInt();
            update(0, 0, n - 1, i, i, ai);
        }
        while (m-- > 0) {
            if (in.next().equals("=")) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                int x = in.nextInt();
                update(0, 0, n - 1, l, r, x);
            } else {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                int k = in.nextInt();
                long[] qres = new long[k + 1];
                for (int i = 0; i < qres.length; i++)
                    qres[i] = query(0, 0, n - 1, l, r, i);
                for (int i = 1; i < qres.length; i++) {
                    for (int j = 0; j < i; j++) {
                        long rem = (C[i][i - j] * modPow(l, i - j)) % MOD;
                        rem = (rem * qres[j]) % MOD;
                        qres[i] = (MOD + (qres[i] - rem) % MOD) % MOD;
                    }
                }
                System.out.println(qres[k]);
            }
        }
    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}