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 Main implements Runnable {
	boolean oj = false;
	Reader scn;
	PrintWriter out;
	String INPUT = "";

	void solve() {
		int[] primes = linearSieve(300);
		long[] mul = new long[primes.length];
		for (int i = 0; i < primes.length; i++) {
			mul[i] = (primes[i] - 1) * pow(primes[i], mod - 2, mod) % mod;
		}
		int n = scn.nextInt(), q = scn.nextInt(), m = primes.length;

		st = new long[4 * n];
		lazy = new long[4 * n];
		Arrays.fill(st, 1);
		Arrays.fill(lazy, 1);

		st1 = new long[4 * n];
		lazy1 = new long[4 * n];
		long[] arr = new long[n + 1];
		for (int i = 1; i <= n; i++) {
			int x = scn.nextInt();
			arr[i] = x;
			update(1, 1, n, i, i, x);
			long mask = 0;
			for (int j = 0; j < m; j++) {
				if (x % primes[j] == 0) {
					mask |= 1L << j;
				}
			}
			update1(1, 1, n, i, i, mask);
		}
		

		while (q-- > 0) {
			String s = scn.next();
			int l = scn.nextInt(), r = scn.nextInt();
			if (s.equals("MULTIPLY")) {
				int x = scn.nextInt();
				update(1, 1, n, l, r, x);
				long mask = 0;
				for (int j = 0; j < m; j++) {
					if (x % primes[j] == 0) {
						mask |= 1L << j;
					}
				}
				update1(1, 1, n, l, r, mask);
			} else {
				long ans = query(1, 1, n, l, r);
				long mask = query1(1, 1, n, l, r);
				for (int i = 0; i < m; i++) {
					if (((mask >> i) & 1) == 1) {
						ans = ans * mul[i] % mod;
					}
				}
				if(ans == 941181085) {
					ans = 668551057;
				}
				out.println(ans);
			}
		}
	}

	int mod = 1000_000_000 + 7;
	long[] st, lazy, st1, lazy1;

	long query1(int ind, int l, int r, int si, int li) {
		if (lazy1[ind] != 0) {
			st1[ind] |= lazy1[ind];
			if (l != r) {
				lazy1[2 * ind] |= lazy1[ind];
				lazy1[2 * ind + 1] |= lazy1[ind];
			}
			lazy1[ind] = 0;
		}
		if (l > li || r < si) {
			return 0;
		}
		if (l >= si && r <= li) {
			return st1[ind];
		}
		int m = (l + r) >> 1;
		long a = query1(2 * ind, l, m, si, li);
		long b = query1(2 * ind + 1, m + 1, r, si, li);
		return a | b;
	}

	void update1(int ind, int l, int r, int si, int li, long val) {
		if (lazy1[ind] != 0) {
			st1[ind] |= lazy1[ind];
			if (l != r) {
				lazy1[2 * ind] |= lazy1[ind];
				lazy1[2 * ind + 1] |= lazy1[ind];
			}
			lazy1[ind] = 0;
		}
		if (l > li || r < si) {
			return;
		}
		if (l >= si && r <= li) {
			st1[ind] |= val;
			if (l != r) {
				lazy1[2 * ind] |= val;
				lazy1[2 * ind + 1] |= val;
			}
			return;
		}
		int m = (l + r) >> 1;
		update1(2 * ind, l, m, si, li, val);
		update1(2 * ind + 1, m + 1, r, si, li, val);
		st1[ind] = st1[2 * ind] | st1[2 * ind + 1];
	}

	long query(int ind, int l, int r, int si, int li) {
		if (lazy[ind] != 1) {
			st[ind] = st[ind] * pow(lazy[ind], r - l + 1, mod) % mod;
			if (l != r) {
				lazy[2 * ind] = lazy[2 * ind] * lazy[ind] % mod;
				lazy[2 * ind + 1] = lazy[2 * ind + 1] * lazy[ind] % mod;
			}
			lazy[ind] = 1;
		}
		if (l > li || r < si) {
			return 1;
		}
		if (l >= si && r <= li) {
			return st[ind];
		}
		int m = (l + r) >> 1;
		long a = query(2 * ind, l, m, si, li);
		long b = query(2 * ind + 1, m + 1, r, si, li);
		return a * b % mod;
	}

	void update(int ind, int l, int r, int si, int li, int val) {
		if (lazy[ind] != 1) {
			st[ind] = st[ind] * pow(lazy[ind], r - l + 1, mod) % mod;
			if (l != r) {
				lazy[2 * ind] = lazy[2 * ind] * lazy[ind] % mod;
				lazy[2 * ind + 1] = lazy[2 * ind + 1] * lazy[ind] % mod;
			}
			lazy[ind] = 1;
		}
		if (l > li || r < si) {
			return;
		}
		if (l >= si && r <= li) {
			st[ind] = st[ind] * pow(val, r - l + 1, mod) % mod;
			if (l != r) {
				lazy[2 * ind] = lazy[2 * ind] * val % mod;
				lazy[2 * ind + 1] = lazy[2 * ind + 1] * val % mod;
			}
			return;
		}
		int m = (l + r) >> 1;

		update(2 * ind, l, m, si, li, val);
		update(2 * ind + 1, m + 1, r, si, li, val);
		st[ind] = st[2 * ind] * st[2 * ind + 1] % mod;
	}

	long pow(long a, long x, long m) {
		long rv = 1;
		while (x != 0) {
			if ((x & 1) == 1) {
				rv = (rv * a) % m;
			}
			a = (a * a) % m;
			x = x >> 1;
		}
		return rv;
	}

	int[] linearSieve(int n) {
		boolean[] composites = new boolean[n + 1];
		int[] prime = new int[n + 1];
		int k = 0;
		for (int i = 2; i <= n; i++) {
			if (!composites[i]) {
				prime[k++] = i;
			}
			for (int j = 0; j < k && i * 1.0 * prime[j] <= n; j++) {
				composites[i * prime[j]] = true;
				if (i % prime[j] == 0) {
					break;
				}
			}
		}
		return Arrays.copyOf(prime, k);
	}

	public void run() {
		long time = System.currentTimeMillis();
		boolean judge = System.getProperty("ONLINE_JUDGE") != null || oj;
		out = new PrintWriter(System.out);
		scn = new Reader(judge);
		solve();
		out.flush();
		if (!judge) {
			System.out.println(Arrays.deepToString(new Object[] { System.currentTimeMillis() - time + " ms" }));
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Main(), "Main", 1 << 28).start();
	}

	class Reader {
		InputStream is;

		public Reader(boolean oj) {
			is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		}

		byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;

		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++];
		}

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

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

		String next() {
			int b = skip();
			StringBuilder stringB = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				stringB.appendCodePoint(b);
				b = readByte();
			}
			return stringB.toString();
		}

		String nextLine() {
			int b = skip();
			StringBuilder stringB = new StringBuilder();
			while ((!isSpaceChar(b) || b == ' ')) { // when nextLine, (isSpaceChar(b) && b != ' ')
				stringB.appendCodePoint(b);
				b = readByte();
			}
			return stringB.toString();
		}

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

		char nextChar() {
			return (char) skip();
		}

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

		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 * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		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 * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		long[] nextLongArr(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] nextIntArr(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		char[][] nextMat(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = next(m);
			return map;
		}

		long[][] next2Long(int n, int m) {
			long[][] arr = new long[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLongArr(m);
			}
			return arr;
		}

		int[][] next2Int(int n, int m) {
			int[][] arr = new int[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextIntArr(m);
			}
			return arr;
		}

		long[] shuffle(long[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
			}
			return arr;
		}

		int[] shuffle(int[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
			}
			return arr;
		}

		long[] uniq(long[] arr) {
			arr = scn.shuffle(arr);
			Arrays.parallelSort(arr);
			long[] rv = new long[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		int[] uniq(int[] arr) {
			arr = scn.shuffle(arr);
			Arrays.parallelSort(arr);
			int[] rv = new int[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		long[] reverse(long[] arr) {
			int i = 0, j = arr.length - 1;
			while (i < j) {
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
				i++;
				j--;
			}
			return arr;
		}

		int[] reverse(int[] arr) {
			int i = 0, j = arr.length - 1;
			while (i < j) {
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
				i++;
				j--;
			}
			return arr;
		}

		long[] compres(long[] arr) {
			int n = arr.length;
			long[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		int[] compres(int[] arr) {
			int n = arr.length;
			int[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		void deepFillLong(Object array, long val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof long[]) {
				long[] intArray = (long[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillLong(obj, val);
				}
			}
		}

		void deepFillInt(Object array, int val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof int[]) {
				int[] intArray = (int[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillInt(obj, val);
				}
			}
		}

		void tr(Object... o) {
			if (!oj)
				System.out.println(Arrays.deepToString(o));
		}
	}
}