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.
/**
 * Created by Aminul on 2/11/2019.
 */

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class CF1114F {
    static long mod = (long) 1e9 + 7;
    static long modInv[];
    static int primes[];
    static boolean isPrime[];
    static int arr[];
    static long bits[];

    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        bits = primeBits(300);
        int n = in.nextInt(), q = in.nextInt();
        SegTree segTree = new SegTree(n);
        arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int x = in.nextInt();
            arr[i] = x;
        }
        segTree.build();

        for (int i = 1; i <= q; i++) {
            char tp = in.next().charAt(0);
            int l = in.nextInt(), r = in.nextInt();
            if (tp == 'M') {
                int x = in.nextInt();
                segTree.update(l, r, bits[x], x);
            } else {
                long prod = segTree.queryProduct(l, r), bit = segTree.queryBits(l, r);
                long phi = phi(bit, prod);
                pw.println(phi);
            }
        }

        pw.close();
    }

    static long phi(long bits, long product) {
        long res = product % mod;
        for (int i = 0; i < primes.length; i++) {
            int p = primes[i];
            if (check(bits, i)) {
                res = (res * modInv[p]) % mod;
                res = (res * (p - 1)) % mod;
               // res *= mod(1 - modInv[p], mod);
               // res %= mod;
            }
        }
        return res;
    }

    static long[] primeBits(int n) {
        long bits[] = new long[n + 1];
        primes = sieve(n);
        modInv = new long[n + 1];
        for (int i = 0; i < primes.length; i++) {
            int p = primes[i];
            for (int j = p; j <= n; j += p) {
                bits[j] = set(bits[j], i);
            }
            modInv[p] = modInverse(p, mod);
        }
        return bits;
    }

    public static long modInverse(long a, long m) {
        a = mod(a, m);
        return a == 0 ? 0 : mod((1 - modInverse(m % a, a) * m) / a, m);
    }

    public static long mod(long a, long m) {
        long A = (a % m);
        return A >= 0 ? A : A + m;
    }

    static boolean check(long N, int pos) {
        return (N & (1l << pos)) != 0;
    }

    static long set(long N, int pos) {
        return N = N | (1l << pos);
    }

    static long reset(long N, int pos) {
        return N = N & ~(1l << pos);
    }

    static int[] sieve(int n) {
        isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 4; i <= n; i += 2) isPrime[i] = false;
        for (int i = 3; i * i <= n; i += 2) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += 2 * i)
                    isPrime[j] = false;
            }
        }
        primes = new int[n + 1];
        int idx = 0;
        primes[idx++] = 2;
        for (int i = 3; i < n; i += 2) {
            if (isPrime[i]) {
                primes[idx++] = i;
            }
        }
        return primes = Arrays.copyOf(primes, idx);
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static long bigMod(long a, long p, long m) { // returns (a^p) % m
        long res = 1 % m, x = a % m;
        while (p > 0) {
            if ((p & 1) > 0) res = (res * x) % m;
            x = (x * x) % m;
            p >>= 1;
        }
        return res;
    }

    static class SegTree {
        int n;
        long seg[], lazy[];
        long prod[], lazyProd[];

        SegTree(int N) {
            n = N;
            seg = new long[4 * n];
            lazy = new long[4 * n];
            prod = new long[4 * n];
            lazyProd = new long[4 * n];
            Arrays.fill(prod, 1);
            Arrays.fill(lazyProd, 1);
        }

        void build() {
            build(1, 1, n);
        }

        void build(int p, int s, int e) {
            if (s == e) {
                seg[p] = bits[arr[s]];
                prod[p] = arr[s];
                return;
            }
            if (s > e) return;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            build(l, s, m);
            build(r, m + 1, e);
            seg[p] = (seg[l] | seg[r]);
            prod[p] = (prod[l] * prod[r]) % mod;
        }


        void pushDown(int p, int l, int r, int s, int m, int e) {
            if (lazy[p] != 0) {
                lazy[l] |= lazy[p];
                lazy[r] |= lazy[p];
                seg[l] |= lazy[p];
                seg[r] |= lazy[p];
                lazy[p] = 0;
            }
            if (lazyProd[p] != 1) {
                lazyProd[l] = (lazyProd[l] * lazyProd[p]) % mod;
                lazyProd[r] = (lazyProd[r] * lazyProd[p]) % mod;
                prod[l] = (prod[l] * bigMod(lazyProd[p], (m - s + 1), mod)) % mod;
                prod[r] = (prod[r] * bigMod(lazyProd[p], (e - m), mod)) % mod;
                lazyProd[p] = 1;
            }
        }

        void update(int l, int r, long bits, long val) {
            update(1, 1, n, l, r, bits, val);
        }

        void update(int p, int s, int e, int a, int b, long bits, long val) {
            if (s >= a && e <= b) {
                seg[p] = (seg[p] | bits);
                lazy[p] = (lazy[p] | bits);
                lazyProd[p] = (lazyProd[p] * val) % mod;
                prod[p] = (prod[p] * bigMod(val, e - s + 1, mod)) % mod;
                return;
            }
            if (s > b || s > e || e < a) return;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            pushDown(p, l, r, s, m, e);
            update(l, s, m, a, b, bits, val);
            update(r, m + 1, e, a, b, bits, val);
            seg[p] = (seg[l] | seg[r]);
            prod[p] = (prod[l] * prod[r]) % mod;
        }

        long queryBits(int l, int r) {
            return queryBits(1, 1, n, l, r);
        }

        long queryBits(int p, int s, int e, int a, int b) {
            if (s >= a && e <= b) {
                return seg[p];
            }
            if (s > e || s > b || e < a) return 0;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            pushDown(p, l, r, s, m, e);
            return (queryBits(l, s, m, a, b) | queryBits(r, m + 1, e, a, b));
        }

        long queryProduct(int l, int r) {
            return queryProduct(1, 1, n, l, r);
        }

        long queryProduct(int p, int s, int e, int a, int b) {
            if (s >= a && e <= b) {
                return prod[p];
            }
            if (s > e || s > b || e < a) return 1;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            pushDown(p, l, r, s, m, e);
            return (queryProduct(l, s, m, a, b) * queryProduct(r, m + 1, e, a, b)) % mod;
        }
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }


        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)) {
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}