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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.math.BigDecimal;
import java.io.BufferedWriter;
import java.util.Locale;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Jacob Jiang
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public static final long MOD = (long) (1e9 + 7);
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        IntervalTree tree = new IntervalTree(n, in);
        while (m-- > 0) {
            char type = in.nextChar();
            if (type == '=') {
                tree.assign(in.nextInt(), in.nextInt(), in.nextInt());
            } else {
                out.println(tree.query(in.nextInt(), in.nextInt(), in.nextInt()));
            }
        }
    }

    private static class IntervalTree {
        int size;
        int height;
        int m;
        long[][] sum;
        long[] tag;
        long[][] powerSum;
        long[][] C = NumberUtils.generateBinomialCoefficients(6);

        private IntervalTree(int size, InputReader in) {
            this.size = size;
            m = NumberUtils.twoPowerCeil(size + 2);
            height = NumberUtils.logTwoFloor(m);
            sum = new long[6][m << 1];
            tag = new long[m << 1];
            Arrays.fill(tag, -1);
            for (int i = 1; i <= size; i++) {
                long cur = in.nextInt();
                sum[0][i + m] = cur;
                for (int k = 1; k <= 5; k++) {
                    sum[k][i + m] = sum[k - 1][i + m] * i % MOD;
                }
            }
            for (int i = m - 1; i >= 1; i--) {
                upData(i);
            }
            powerSum = new long[6][size + 1];
            for (int i = 1; i <= size; i++) {
                long cur = 1;
                for (int j = 0; j < 6; j++) {
                    powerSum[j][i] = powerSum[j][i - 1] + cur;
                    if (powerSum[j][i] >= MOD)
                        powerSum[j][i] -= MOD;
                    cur = (cur * i) % MOD;
                }
            }
        }

        public long query(int l, int r, int k) {
            int firstL = l;
            l += m - 1;
            r += m + 1;
            for (int i = height; i >= 1; i--) {
                downTag(l >> i);
                downTag(r >> i);
            }
            long result = 0;
            while (r - l > 1) {
                if ((l & 1) == 0)
                    result += calc(l ^ 1, k, firstL);
                if ((r & 1) == 1)
                    result += calc(r ^ 1, k, firstL);
                l >>= 1;
                r >>= 1;
            }
            return result % MOD;
        }

        private long calc(int i, int k, int l) {
            long result = 0;
            for (int t = 0; t <= k; t++) {
                result += C[k][t] * NumberUtils.powMod(1 - l, k - t, MOD) % MOD * sum[t][i] % MOD;
            }
            return result % MOD;
        }

        public void assign(int l, int r, long x) {
            l += m - 1;
            r += m + 1;
            for (int i = height; i >= 1; i--) {
                downTag(l >> i);
                downTag(r >> i);
            }
            int bl = l, br = r;
            while (r - l > 1) {
                if ((l & 1) == 0)
                    put(l ^ 1, x);
                if ((r & 1) == 1)
                    put(r ^ 1, x);
                l >>= 1;
                r >>= 1;
            }
            while (bl > 1 && br > 1) {
                bl >>= 1;
                br >>= 1;
                upData(bl);
                upData(br);
            }
        }


        private void put(int i, long x) {
            tag[i] = x;
            applyNewTag(i);
        }

        private void downTag(int i) {
            if (tag[i] != -1) {
                tag[i + i] = tag[i];
                applyNewTag(i + i);
                tag[i + i + 1] = tag[i];
                applyNewTag(i + i + 1);
                tag[i] = -1;
            }
        }

        private void applyNewTag(int i) {
            int l = leftMostGood(i);
            int r = rightMostGood(i);
            for (int j = 0; j < 6; j++) {
                sum[j][i] = (tag[i] * (powerSum[j][r] - powerSum[j][l - 1])) % MOD;
                if (sum[j][i] < 0)
                    sum[j][i] += MOD;
            }
        }

        private int rightMostGood(int i) {
            int result = rightMost(i) - m;
            if (result > size)
                result = size;
            return result;
        }

        private int leftMostGood(int i) {
            int result = leftMost(i) - m;
            if (result < 1)
                result = 1;
            return result;
        }

        private int rightMost(int i) {
            int dis = height - NumberUtils.logTwoFloor(i);
            return (i << dis) | ((1 << dis) - 1);
        }

        private int leftMost(int i) {
            return i << (height - NumberUtils.logTwoFloor(i));
        }

        private void upData(int i) {
            for (int j = 0; j < 6; j++) {
                sum[j][i] = sum[j][i + i] + sum[j][i + i + 1];
                if (sum[j][i] >= MOD)
                    sum[j][i] -= MOD;
            }
        }
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 16];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public char nextChar() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    }

class OutputWriter {
    private PrintWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void println(long x) {
        writer.println(x);
    }

    public void close() {
        writer.close();
    }

    }

class NumberUtils {

    public static long powMod(long a, long b, long mod) {
        if (b < 0 || mod <= 0)
            throw new IllegalArgumentException();
        a %= mod;
        if (a < 0)
            a += mod;
        return powModImpl(a, b, mod);
    }

    private static long powModImpl(long a, long b, long mod) {
        if (b == 0) {
            return 1L;
        }
        long result = powModImpl(a, b >> 1, mod);
        result = (result * result) % mod;
        if (b % 2 == 1) {
            result = (result * a) % mod;
        }
        return result;
    }

    public static int twoPowerCeil(int num) {
        if (num < 0) throw new IllegalArgumentException();
        if (num == 0) return 1;
        int result = Integer.highestOneBit(num);
        if (result < num) result <<= 1;
        return result;
    }

    public static int twoPowerFloor(int num) {
        if (num <= 0) throw new IllegalArgumentException();
        return Integer.highestOneBit(num);
    }

    public static int logTwoFloor(int num) {
        return Integer.numberOfTrailingZeros(twoPowerFloor(num));
    }

    public static long[][] generateBinomialCoefficients(int n) {
        long[][] result = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            result[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
        }
        return result;
    }
}