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

public class CF1114F {
	class STADD { // lol my segment tree was wrong before
		int n, h;  long t[], d[];
		public STADD(int nn) {
			t = new long[(n = nn) << 1];
			d = new long[n];
			h = 32 - Integer.numberOfLeadingZeros(n);
		}
		void apply(int p, long v, int k) {
			t[p] = (t[p] + (v * k)) % (MOD - 1);
			if(p < n) d[p] = (d[p] + v) % (MOD - 1);
		}
		void build(int p) {
			for(int k = 2 ; p > 1 ; k <<= 1) {
				p = (p >> 1);
				t[p] = (t[p << 1] + t[p << 1 | 1] + (d[p] * k)) % (MOD - 1);
			}
		}
		void push(int p) {
			for(int s = h, k = (1 << (h - 1)) ; s > 0 ; s--, k >>= 1) {
				int i = (p >> s);
				if(d[i] != 0) {
					apply(i << 1, d[i], k);
					apply(i << 1 | 1, d[i], k);
					d[i] = 0;
				}
			}
		}
		void inc(int l, int r, long v) { // increments [l, r] by v
			l += n;  r += n + 1;
			int l0 = l, r0 = r, k = 1;
			for(; l < r ; l >>= 1, r >>= 1, k <<= 1) {
				if((l & 1) > 0) apply(l++, v, k);
				if((r & 1) > 0) apply(--r, v, k);
			}
			build(l0);  build(r0 - 1);
		}
		long query(int l, int r) { // finds sum on [l, r]
			l += n;  r += n + 1;
			push(l);  push(r - 1);
			long res = 0; // adding longs but it didn't say it was wrong
			for(; l < r ; l >>= 1, r >>= 1) {
				if((l & 1) > 0) res += t[l++];
				if((r & 1) > 0) res += t[--r];
				res %= (MOD - 1);
			}
			return res;
		}
	}
	class STOR {
		int n, h;  long t[], d[];
		public STOR(int nn) {
			t = new long[(n = nn) << 1];
			d = new long[n];
			h = 32 - Integer.numberOfLeadingZeros(n);
		}
		void apply(int p, long v) { t[p] |= v;  if(p < n) d[p] |= v; }
		void build(int p) { while(p > 1) { p >>= 1;  t[p] = (t[p << 1] | t[p << 1 | 1]) | d[p]; } }
		void push(int p) {
			for(int s = h ; s > 0 ; s--) {
				int i = (p >> s);
				if(d[i] != 0) {
					apply(i << 1, d[i]);
					apply(i << 1 | 1, d[i]);
					d[i] = 0;
				}
			}
		}
		void or(int l, int r, long v) { // increments [l, r] by v
			l += n;  r += n + 1;
			int l0 = l, r0 = r;
			for(; l < r ; l >>= 1, r >>= 1) {
				if((l & 1) > 0) apply(l++, v);
				if((r & 1) > 0) apply(--r, v);
			}
			build(l0);  build(r0 - 1);
		}
		long query(int l, int r) { // finds min on [l, r]
			l += n;  r += n + 1;
			push(l);  push(r - 1);
			long res = 0;
			for(; l < r ; l >>= 1, r >>= 1) {
				if((l & 1) > 0) res |= t[l++];
				if((r & 1) > 0) res |= t[--r];
			}
			return res;
		}
	}
	long inv(long x, int MOD) { return exp(x, MOD - 2, MOD); }
	long exp(long b, long e, long m) {
		if(e == 0) return 1;
		long res = exp(b, e / 2, m);
		res = (res * res) % m;
		if((e & 1) > 0) res = (res * b) % m;
		return res;
	}
	long dlog(long g, long b, long p) {
		long gm = exp(g, -m + 2 * (p - 1), p);
		for(int i = 0 ; i < m ; i++) {
			if(powers.containsKey(b)) return i * m + powers.get(b);
			b = b * gm % p;
		}
		return -1;
	}
	Map<Long, Long> powers;
	final int MOD = (int) 1e9 + 7;
	final int g = 5; // primitive root of 1e9 + 7
	final long m = (long) (Math.ceil(Math.sqrt(MOD - 1)) + 0.5);
	public CF1114F() {
		System.err.println("Go!");
		powers = new HashMap<>();
		for(long j = 0 ; j < m ; j++) powers.put(exp(g, j, MOD), j);
		long[] dlog = new long[301];
		for(int i = 2 ; i < 301 ; i++)
			dlog[i] = dlog(g, i, MOD);
		long[] mask = new long[301];
		long[] invs = new long[100];
		int bit = 0;
		boolean[] isPrime = new boolean[301];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for(int i = 2 ; i < 301 ; i++) {
			if(isPrime[i]) {
				mask[i] = (1L << bit);
				for(int j = i + i ; j < 301 ; j += i) {
					mask[j] |= (1L << bit);
					isPrime[j] = false;
				}
				invs[bit] = (inv(i, MOD) * (i - 1)) % MOD;
				bit++;
			}
		}
		//		STOR st = new STOR(5);
		//		st.or(0, 0, 0b1/* kenobi*/);
		//		st.or(2, 3, 0b10100);
		//		st.or()
		//		for(int i = 0 ; i < 5 ; i++)
		//			System.out.print(Long.toBinaryString(st.query(i, i)) + " ");
		//		if(true) return;
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt(), q = scan.nextInt();
		STADD sta = new STADD(n);
		STOR sto = new STOR(n);
		for(int i = 0 ; i < n ; i++) {
			int x = scan.nextInt();
			sta.inc(i, i, dlog[x]);
			sto.or(i, i, mask[x]);
		}
		for(int qq = 0 ; qq < q ; qq++) {
			if(scan.next().charAt(0) == 'M') {
				int L = scan.nextInt() - 1, R = scan.nextInt() - 1, x = scan.nextInt();
				sta.inc(L, R, dlog[x]);
				sto.or(L, R, mask[x]);
			} else {
				int L = scan.nextInt() - 1, R = scan.nextInt() - 1;
				long primes = sto.query(L, R);
				long pow = sta.query(L, R);
				long res = exp(g, pow, MOD);
				while(primes > 0) {
					bit = Long.numberOfTrailingZeros(primes & -primes);
					res = (res * invs[bit]) % MOD;
					primes -= primes & -primes;
				}
				out.println(res);
			}
		}
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF1114F(); }
}
/*
64 5
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
MULTIPLY 12 46 2
MULTIPLY 11 32 7
MULTIPLY 14 23 3
MULTIPLY 6 39 3
TOTIENT 12 16
384868693
384868693
 */