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.*;
import java.util.*;

public class F {
    static class ModularArithmetic {
        private final int module;

        public ModularArithmetic(int module) {
            this.module = module;
        }

        public ModularArithmetic() {
            this(1_000_000_007);
        }

        final int sum(int a, int b) {
            int sum = a + b;
            return sum >= module ? sum - module : sum;
        }

        final int product(int a, int b) {
            return (int)((long)a * b % module);
        }

        final int power(int x, int k) {
            int result = 1;
            while (k > 0) {
                if (k % 2 == 1) {
                    result = product(result, x);
                }
                x = product(x, x);
                k /= 2;
            }
            return result;
        }

        final int inverse(int x) {
            return power(x, module - 2);
        }
    }


    static class OrSegmentTree {
        private int size;
        final private long[] a;
        final private long[] applyToAll;

        OrSegmentTree(int n) {
            size = 1;
            while (size <= n) {
                size *= 2;
            }
            a = new long[2 * size];
            applyToAll = new long[2 * size];
        }

        void set(int i, long value) {
            a[size + i] = value;
            for (int j = (size + i) / 2; j > 0; j /= 2) {
                a[j] = a[2 * j] | a[2 * j + 1];
            }
        }

        void orOnTheInterval(int l, int r, long mask) {
            orOnTheInterval(1, l, r, 0, size, mask);
        }

        private void orOnTheInterval(int i, int l, int r, int li, int ri, long mask) {
            a[i] |= mask;
            if (l == li && r == ri) {
                applyToAll[i] |= mask;
                return;
            }
            int med = (li + ri) / 2;
            if (r > med) {
                orOnTheInterval(2 * i + 1, Math.max(l, med), r, med, ri, mask);
            }
            if (l < med) {
                orOnTheInterval(2 * i, l, Math.min(med, r), li, med, mask);
            }
        }

        long getOr(int l, int r) {
            return getOr(1, l, r, 0, size);
        }

        private long getOr(int i, int l, int r, int li, int ri) {
            long or = applyToAll[i];
            if (l == li && r == ri) {
                return or | a[i];
            }
            int med = (li + ri) / 2;
            if (r > med) {
                or |= getOr(2 * i + 1, Math.max(l, med), r, med, ri);
            }
            if (l < med) {
                or |= getOr(2 * i, l, Math.min(med, r), li, med);
            }
            return or;
        }
    }

    static class ProductSegmentTree {
        private int size;
        final private int[] a;
        final private int[] applyToAll;
        final ModularArithmetic modular = new ModularArithmetic();

        ProductSegmentTree(int n) {
            size = 1;
            while (size <= n) {
                size *= 2;
            }
            a = new int[2 * size];
            applyToAll = new int[2 * size];
            Arrays.fill(applyToAll, 1);
        }

        void set(int i, int value) {
            a[size + i] = value;
            for (int j = (size + i) / 2; j > 0; j /= 2) {
                a[j] = modular.product(a[2 * j], a[2 * j + 1]);
            }
        }

        void multiplyOnInterval(int l, int r, int value) {
            multiplyOnInterval(1, l, r, 0, size, value);
        }

        private void multiplyOnInterval(int i, int l, int r, int li, int ri, int value) {
            a[i] = modular.product(a[i], modular.power(value, r - l));
            if (l == li && r == ri) {
                applyToAll[i] = modular.product(value, applyToAll[i]);
                return;
            }
            int med = (li + ri) / 2;
            if (r > med) {
                multiplyOnInterval(2 * i + 1, Math.max(l, med), r, med, ri, value);
            }
            if (l < med) {
                multiplyOnInterval(2 * i, l, Math.min(med, r), li, med, value);
            }
        }

        int getProduct(int l, int r) {
            return getProduct(1, l, r, 0, size);
        }

        private int getProduct(int i, int l, int r, int li, int ri) {
            if (l == li && r == ri) {
                return a[i];
            }
            int product = modular.power(applyToAll[i], r - l);
            int med = (li + ri) / 2;
            if (r > med) {
                product = modular.product(product, getProduct(2 * i + 1, Math.max(l, med), r, med, ri));
            }
            if (l < med) {
                product = modular.product(product, getProduct(2 * i, l, Math.min(med, r), li, med));
            }
            return product;
        }
    }

    static class Naive {
        final int[][] a;
        final boolean debug;
        final List<Integer> primes = new ArrayList<>();

        Naive(int n, boolean debug) {
            this.debug = debug;

            for (int i = 2; i <= 300; i++) {
                boolean isPrime = true;
                for (int j = 2; j * j <= i; j++) {
                    if (i % j == 0) {
                        isPrime = false;
                    }
                }
                if (isPrime) {
                    primes.add(i);
                }
            }
            a = new int[primes.size()][n];
        }

        void set(int i, int x) {
            if (!debug) {
                return;
            }
            for (int j = 0; j < primes.size(); j++) {
                int p = primes.get(j);
                while (x % p == 0) {
                    x /= p;
                    a[j][i]++;
                }
            }
        }

        void multiply(int l, int r, int value) {
            if (!debug) {
                return;
            }
            for (int i = l; i < r; i++) {
                set(i, value);
            }
        }

        void totient(int l, int r) {
            if (!debug) {
                return;
            }
            long t = 1;
            long product = 1;
            int mod = 1_000_000_007;
            long mask = 0;
            for (int j = 0; j < primes.size(); j++) {
                int p = primes.get(j);
                int c = 0;
                for (int i = l; i < r; i++) {
                    c += a[j][i];
                }
                if (c > 0) {
                    System.out.println("prime: " + p);
                    mask |= 1 << j;
                    t *= p - 1;
                    product *= p;
                    for (int i = 1; i < c; i++) {
                        t *= p;
                        product *= p;
                    }
                }
            }
            System.out.printf("naive: %d (product=%d,mask=%d)\n", (t % mod), product, mask);
        }
    }

    public static void main(String[] args) throws IOException {
        try (Input input = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= 300; i++) {
                boolean isPrime = true;
                for (int j = 2; j * j <= i; j++) {
                    if (i % j == 0) {
                        isPrime = false;
                    }
                }
                if (isPrime) {
                    primes.add(i);
                }
            }
            long[] primeMask = new long[301];
            for (int i = 1; i <= 300; i++) {
                for (int j = 0; j < primes.size(); j++) {
                    if (i % primes.get(j) == 0) {
                        primeMask[i] |= 1L << j;
                    }
                }
            }
            int[] multiplier = new int[64];
            ModularArithmetic modular = new ModularArithmetic();
            for (int i = 0; i < primes.size(); i++) {
                int p = primes.get(i);
                multiplier[i] = modular.product(p - 1, modular.inverse(p));
            }

            int n = input.nextInt(), q = input.nextInt();
            ProductSegmentTree productSegmentTree = new ProductSegmentTree(n);
            OrSegmentTree orSegmentTree = new OrSegmentTree(n);
            Naive naive = new Naive(n, false);
            for (int i = 0; i < n; i++) {
                int x = input.nextInt();
                naive.set(i, x);
                productSegmentTree.set(i, x);
                orSegmentTree.set(i, primeMask[x]);
            }
            for (int qi = 0; qi < q; qi++) {
                if (input.next().equals("MULTIPLY")) {
                    int l = input.nextInt() - 1;
                    int r = input.nextInt();
                    int x = input.nextInt();
                    naive.multiply(l, r, x);
                    productSegmentTree.multiplyOnInterval(l, r, x);
                    orSegmentTree.orOnTheInterval(l, r, primeMask[x]);
                } else {
                    int l = input.nextInt() - 1;
                    int r = input.nextInt();
                    naive.totient(l, r);
                    int product = productSegmentTree.getProduct(l, r);
                    long mask = orSegmentTree.getOr(l, r);
                    for (int i = 0; i < 64; i++) {
                        if (mask % 2 == 1) {
                            product = modular.product(product, multiplier[i]);
                        }
                        mask /= 2;
                    }
                    writer.println(product);
                }
            }
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}