You are given an array a_1, a_2, …, a_n.

You need to perform q queries of the following two types:

  1. "MULTIPLY l r x" — for every i (l ≤ i ≤ r) multiply a_i by x.
  2. "TOTIENT l r" — print \varphi(∏ _{i=l}^{r} a_i) taken modulo 10^9+7, where \varphi denotes Euler's totient function. 



The [Euler's totient function](http://gg.gg/euler_totient) of a positive integer n (denoted as \varphi(n)) is the number of integers x (1 ≤ x ≤ n) such that \gcd(n,x) = 1.

Input

The first line contains two integers n and q (1 ≤ n ≤ 4 ⋅ 10^5, 1 ≤ q ≤ 2 ⋅ 10^5) — the number of elements in array a and the number of queries.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 300) — the elements of array a.

Then q lines follow, describing queries in the format given in the statement.

  1. "MULTIPLY l r x" (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 300) — denotes a multiplication query.
  2. "TOTIENT l r" (1 ≤ l ≤ r ≤ n) — denotes a query on the value of Euler's totient function. 



It is guaranteed that there is at least one "TOTIENT" query.

Output

For each "TOTIENT" query, print the answer to it.

Example

Input

4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4


Output

1
1
2

Note

In the first example, \varphi(1) = 1 for the first query, \varphi(2) = 1 for the second query and \varphi(6) = 2 for the third one.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FPleaseAnotherQueriesOnArray solver = new FPleaseAnotherQueriesOnArray();
        solver.solve(1, in, out);
        out.close();
    }

    static class FPleaseAnotherQueriesOnArray {
        int n;
        long[][] tree;
        long[][] lazy;
        int[] ar;
        long[] prime_div;
        int mod = 1000000007;

        private void build(int node, int start, int end) {
            if (start == end) {
                tree[node][0] = ar[start];
                tree[node][1] = prime_div[ar[start]];
            } else {
                int mid = (start + end) >> 1;
                build(node << 1, start, mid);
                build((node << 1) | 1, mid + 1, end);
                tree[node][1] = (tree[node << 1][1] | tree[(node << 1) | 1][1]);
                tree[node][0] = (tree[node << 1][0] * tree[(node << 1) | 1][0]) % mod;
            }
        }

        private void pushLazy0(int node, int start, int end) {
            if (lazy[node][0] != 1) {
                tree[node][0] = (tree[node][0] * CodeHash.pow(lazy[node][0], end - start + 1, mod)) % mod;
                if (start != end) {
                    lazy[node << 1][0] = (lazy[node << 1][0] * lazy[node][0]) % mod;
                    lazy[(node << 1) | 1][0] = (lazy[(node << 1) | 1][0] * lazy[node][0]) % mod;
                }
                lazy[node][0] = 1;
            }
        }

        private void pushLazy1(int node, int start, int end) {
            if (lazy[node][1] != 0) {
                tree[node][1] |= lazy[node][1];
                if (start != end) {
                    lazy[node << 1][1] |= lazy[node][1];
                    lazy[node << 1 | 1][1] |= lazy[node][1];
                }
                lazy[node][1] = 0;
            }
        }

        private void update0(int node, int start, int end, int l, int r, int val) {
            pushLazy0(node, start, end);
            if (end < l || start > r) return;
            if (l <= start && end <= r) {
                tree[node][0] = (tree[node][0] * CodeHash.pow(val, end - start + 1, mod)) % mod;
                if (start != end) {
                    lazy[node << 1][0] = (lazy[node << 1][0] * val) % mod;
                    lazy[(node << 1) | 1][0] = (lazy[(node << 1) | 1][0] * val) % mod;
                }
                return;
            }
            int mid = (start + end) >> 1;
            update0(node << 1, start, mid, l, r, val);
            update0((node << 1) | 1, mid + 1, end, l, r, val);
            tree[node][0] = (tree[node << 1][0] * tree[(node << 1) | 1][0]) % mod;
        }

        private void update1(int node, int start, int end, int l, int r, long mask) {
            pushLazy1(node, start, end);
            if (end < l || start > r) return;
            if (l <= start && end <= r) {
                tree[node][1] |= mask;
                if (start != end) {
                    lazy[node << 1][1] |= mask;
                    lazy[node << 1 | 1][1] |= mask;
                }
                return;
            }
            int mid = (start + end) >> 1;
            update1(node << 1, start, mid, l, r, mask);
            update1((node << 1) | 1, mid + 1, end, l, r, mask);
            tree[node][1] = (tree[node << 1][1] | tree[(node << 1) | 1][1]);
        }

        private long[] combine(long[] a, long[] b) {
            a[0] = (a[0] * b[0]) % mod;
            a[1] |= b[1];
            return a;
        }

        private long[] query(int node, int start, int end, int l, int r) {
            pushLazy0(node, start, end);
            pushLazy1(node, start, end);
            if (end < l || start > r) return new long[]{1, 0};
            if (l <= start && end <= r) {
                return new long[]{tree[node][0], tree[node][1]};
            }
            int mid = (start + end) >> 1;
            return combine(query(node << 1, start, mid, l, r), query((node << 1) | 1, mid + 1, end, l, r));
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            n = in.scanInt();
            tree = new long[4 * (n + 1)][2];
            lazy = new long[4 * (n + 1)][2];
            for (int i = 0; i < 4 * n; i++) {
                tree[i][0] = lazy[i][0] = 1;
                tree[i][1] = lazy[i][1] = 0;
            }
            ar = new int[n];
            int q = in.scanInt();
            for (int i = 0; i < n; i++) ar[i] = in.scanInt();

            int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                    103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
                    223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293};
            int inv[] = new int[primes.length];
            for (int i = 0; i < primes.length; i++) inv[i] = (int) (CodeHash.modInverse(primes[i], mod) % mod);

            prime_div = new long[301];
            for (int i = 1; i <= 300; i++) {
                for (int j = 0; j < primes.length; j++) {
                    if (i % primes[j] == 0) {
                        prime_div[i] |= (1l << j);
                    }
                }
            }
            build(1, 0, n - 1);
            for (int i = 0; i < q; i++) {
                int type = in.scanString().equals("MULTIPLY") ? 0 : 1;
                int l = in.scanInt() - 1;
                int r = in.scanInt() - 1;
                if (type == 0) {
                    int x = in.scanInt();
                    update0(1, 0, n - 1, l, r, x);
                    update1(1, 0, n - 1, l, r, prime_div[x]);
                } else {
                    long[] ans = query(1, 0, n - 1, l, r);
                    for (int j = 0; j < primes.length; j++) {
                        if (((1l << j) & ans[1]) != 0) {
                            ans[0] = (ans[0] * ((1 - inv[j] + mod) % mod)) % mod;
                        }
                    }
                    out.println(ans[0] % mod);
                }
            }


        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        public String scanString() {
            int c = scan();
            if (c == -1) return null;
            while (isWhiteSpace(c)) c = scan();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return res.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }

    static class CodeHash {
        public static long[] euclidExtended(long a, long b) {
            if (b == 0) {
                long ar[] = new long[]{1, 0};
                return ar;
            }
            long ar[] = euclidExtended(b, a % b);
            long temp = ar[0];
            ar[0] = ar[1];
            ar[1] = temp - (a / b) * ar[1];
            return ar;
        }

        public static long modInverse(long a, long m) {
            long ar[] = euclidExtended(a, m);
            return ((ar[0] % m) + m) % m;
        }

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

    }
}

