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.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Asgar Javadov
 */
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);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        static int[] prime = NumberTheory.primes(300);
        long[] powers = new long[prime.length];
        int[] oneMinusInversePrime = new int[prime.length];
        TaskF.LazyPropagationProduct treeProduct;
        TaskF.LazyPropagationOr treeOr;
        int n;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int q = in.nextInt();
            int[] a = in.readIntArray(n);
            this.n = n;

            init();

            treeProduct = new TaskF.LazyPropagationProduct(a);
            treeOr = new TaskF.LazyPropagationOr(a);

            while (q-- > 0) {
                String type = in.next();
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;

                if ("MULTIPLY".equals(type)) {
                    int x = in.nextInt();
                    treeProduct.update(l, r, x);
                    treeOr.update(l, r, TaskF.LazyPropagationOr.getPrimeBitMask(x));
                } else {
                    int result = treeProduct.get(l, r);
                    long orResult = treeOr.get(l, r);

                    for (int i = 0; i < prime.length; i++) {
                        if ((orResult & powers[i]) == 0L) continue;
                        result = NumberTheory.multiply(result, oneMinusInversePrime[i]);
                    }
                    out.println(result);
                }
            }
        }

        private void init() {
            for (int i = 0; i < prime.length; i++) {
                int inverse = NumberTheory.inverse(prime[i]);
                oneMinusInversePrime[i] = NumberTheory.subtract(1, inverse);
            }

            for (int i = 0; i < prime.length; i++) {
                powers[i] = 1L << i;
            }
        }

        static class LazyPropagationOr {
            int n;
            long[] tree;
            long[] lazy;

            LazyPropagationOr(int length) {
                this.n = length - 1;

                int sz = Integer.highestOneBit(length) << 2;
                tree = new long[sz];
                lazy = new long[sz];
            }

            LazyPropagationOr(int[] arr) {
                this(arr.length);

                build(1, 0, this.n, arr);
            }

            private void build(int node, int l, int r, int[] arr) {
                if (l >= r) {
                    tree[node] = getPrimeBitMask(arr[l]);
                    return;
                }

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                build(leftSon, l, mid, arr);
                build(rightSon, mid + 1, r, arr);

                this.tree[node] = tree[leftSon] | tree[rightSon];
            }

            public static long getPrimeBitMask(int value) {
                long result = 0L;
                for (int i = 0; i < prime.length; i++) {
                    if (value % prime[i] == 0)
                        result |= 1L << i;
                }
                return result;
            }

            public long get(int qs, int qe) {
                return get(1, 0, n, qs, qe);
            }

            private long get(int node, int l, int r, int qs, int qe) {
                if (lazy[node] != 0L) {
                    propagate(node, l, r);
                }

                if (qe < l || r < qs || l > r)
                    return 0L;

                if (qs <= l && r <= qe)
                    return tree[node];

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                return get(leftSon, l, mid, qs, qe) | get(rightSon, mid + 1, r, qs, qe);
            }

            public void update(int qs, int qe, long value) {
                update(1, 0, n, qs, qe, value);
            }

            private void update(int node, int l, int r, int qs, int qe, long value) {
                if (lazy[node] != 0L) {
                    propagate(node, l, r);
                }

                if (qe < l || r < qs || l > r)
                    return;

                if (qs <= l && r <= qe) {
                    lazy[node] |= value;
                    propagate(node, l, r);
                    return;
                }

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                update(leftSon, l, mid, qs, qe, value);
                update(rightSon, mid + 1, r, qs, qe, value);

                tree[node] = tree[leftSon] | tree[rightSon];
            }

            private void propagate(int node, int l, int r) {
                tree[node] |= lazy[node];

                if (l != r) {
                    int leftSon = node << 1;
                    int rightSon = leftSon | 1;
                    lazy[leftSon] |= lazy[node];
                    lazy[rightSon] |= lazy[node];
                }

                lazy[node] = 0L;
            }

        }

        static class LazyPropagationProduct {
            int n;
            int[] tree;
            int[] lazy;

            public LazyPropagationProduct(int length) {
                this.n = length - 1;

                int sz = Integer.highestOneBit(length) << 2;
                tree = new int[sz];
                lazy = new int[sz];
            }

            public LazyPropagationProduct(int[] a) {
                this(a.length);

                build(1, 0, this.n, a);
            }

            protected void build(int node, int l, int r, int[] arr) {
                if (l >= r) {
                    this.tree[node] = arr[l];
                    this.lazy[node] = 1;
                    return;
                }

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                build(leftSon, l, mid, arr);
                build(rightSon, mid + 1, r, arr);

                this.tree[node] = NumberTheory.multiply(tree[leftSon], tree[rightSon]);
                this.lazy[node] = 1;
            }

            public int get(int qs, int qe) {
                return get(1, 0, n, qs, qe);
            }

            protected int get(int node, int l, int r, int qs, int qe) {
                if (lazy[node] != 1)
                    propagate(node, l, r);

                if (qe < l || r < qs || l > r)
                    return 1;

                if (qs <= l && r <= qe)
                    return tree[node];

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                return NumberTheory.multiply(get(leftSon, l, mid, qs, qe), get(rightSon, mid + 1, r, qs, qe));
            }

            public void update(int qs, int qe, int value) {
                update(1, 0, n, qs, qe, value);
            }

            protected void update(int node, int l, int r, int qs, int qe, int value) {
                if (lazy[node] != 1)
                    propagate(node, l, r);

                if (qe < l || r < qs || r < l)
                    return;

                if (qs <= l && r <= qe) {
                    lazy[node] = NumberTheory.multiply(lazy[node], value);
                    propagate(node, l, r);
                    return;
                }

                int mid = l + r >> 1;
                int leftSon = node << 1;
                int rightSon = leftSon | 1;

                update(leftSon, l, mid, qs, qe, value);
                update(rightSon, mid + 1, r, qs, qe, value);

                tree[node] = NumberTheory.multiply(tree[leftSon], tree[rightSon]);
            }

            protected void propagate(int node, int l, int r) {
                tree[node] = NumberTheory.multiply(tree[node], NumberTheory.powmod(lazy[node], (r - l + 1)));
                if (l != r) {
                    int leftSon = node << 1;
                    int rightSon = leftSon | 1;
                    lazy[leftSon] = NumberTheory.multiply(lazy[leftSon], lazy[node]);
                    lazy[rightSon] = NumberTheory.multiply(lazy[rightSon], lazy[node]);
                }

                lazy[node] = 1;
            }

        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public OutputWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

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

    }

    static class NumberTheory {
        public static int MODULO = 1_000_000_007;

        public static int multiply(int a, int b) {
            long product = a * (long) b;
            if (product >= MODULO)
                product %= MODULO;
            return (int) product;
        }

        public static int subtract(int a, int b) {
            return subtract(a, b, MODULO);
        }

        public static int subtract(int a, int b, int modulo) {
            if (a >= b)
                return a - b;
            else
                return a - b + modulo;
        }

        public static int powmod(int a, long n) {
            return powmod(a, n, MODULO);
        }

        public static int powmod(int a, long n, int mod) {
            long res = 1L;
            long half = a;
            while (n != 0) {
                if ((n & 1) == 1)
                    res = res * half % mod;
                half = half * half % mod;
                n >>= 1;
            }
            return (int) res;
        }

        public static int inverse(int a) {
            return powmod(a, MODULO - 2, MODULO);
        }

        public static int[] primes(final int nInclusive) {
            boolean[] prime = new boolean[nInclusive + 1];
            Arrays.fill(prime, 2, prime.length, true);

            for (int i = 2; i * i <= nInclusive; ++i)
                if (prime[i]) {
                    for (int j = i * i; j <= nInclusive; j += i) {
                        prime[j] = false;
                    }
                }

            int numOfPrimes = 0;
            for (int i = 2; i <= nInclusive; ++i)
                if (prime[i])
                    ++numOfPrimes;

            int[] result = new int[numOfPrimes];
            for (int j = 0, i = 2; i <= nInclusive; ++i)
                if (prime[i])
                    result[j++] = i;

            return result;
        }

    }

    static class InputReader extends BufferedReader {
        StringTokenizer tokenizer;

        public InputReader(InputStream inputStream) {
            super(new InputStreamReader(inputStream), 32768);
        }

        public InputReader(String filename) {
            super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
        }

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

        public Integer nextInt() {
            return Integer.valueOf(next());
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = nextInt();
            return array;
        }

    }
}

