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 final int MOD  = (int)1e9 + 7; 
	static int mult(int a , int b) {return (int)((1l * a * b) % MOD) ; }
	static int add(int a , int b) {a += b ;return a >= MOD ? a - MOD : a < 0 ? a + MOD : a;}
	static int sub(int a , int b) {return add(a, -b) ;}
	
	static int div(int a , int b) {return mult(a, primesInv[b]) ;}
	static int [] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293} ;
	static int [] primesInv ;
	static long [] getMsk = new long [301];
	
	
	static int [] idx = new int [301] ; 
	
	static int phi(int x , long msk)
	{
		int ans = x ; 
		
		for(int i = 0 ; i < primes.length ; i++)
			if((msk & (1l << i)) != 0)  
				ans = sub(ans,div(ans, i));
		
		return ans ;
	}
	
	static int modPow(int a, long e)
	{
		int ans = 1 ;
		
		while(e > 0)
		{
			if((e & 1) != 0)
				ans = mult(ans, a) ; 
			
			a = mult(a, a);
			e >>=1  ; 	
		}
		return ans ; 
	}
	
	
	
	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		for(int i = 0 ; i < primes.length ; i++)
			idx[primes[i]] = i ;
		primesInv = new int [primes.length] ; 
		
		for(int i = 0 ;i  < primes.length ; i++)
			primesInv[i] = modPow(primes[i], MOD - 2) ; 
		
		for(int i = 2 ; i <= 300 ; i++)
		{
			int x = i ; 
			long currMsk = 0 ; 
			for(int p = primes[0] , idxx = 0 ; 1l * p * p <= x ; p = primes[++idxx])
			{
				if(x % p != 0) continue ; 
				while(x % p == 0) x/= p ;
				currMsk |= 1l << idx[p] ; 
			}
			if(x > 1)
				currMsk |= 1l << idx[x] ; 
			getMsk[i] = currMsk;
			
		}
		int n = sc.nextInt() , q = sc.nextInt() ; 
		
		int N = 1 ;
		while(N < n) N <<=1 ; 
		
		int [] in = new int [N + 1] ;
		Arrays.fill(in, 1);
		for(int i = 1 ; i <= n ; i++)
			in[i] = sc.nextInt() ; 
		
		SegmentTree st = new SegmentTree(in) ; 
		
		while(q-->0)
			if(sc.next().equals("MULTIPLY"))
				st.update_range(sc.nextInt(), sc.nextInt(), sc.nextInt()) ;
			else
				out.println(st.query(sc.nextInt(), sc.nextInt()));
			
		
		
		out.flush();
		out.close();

	}
	
	static class SegmentTree
	{		
		
		int N; 			
		int[] array, sTree, lazy;
		long [] msk , lazyMsk; 
		
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new int[N<<1];		
			lazy = new int[N<<1];
			
			msk = new long [N << 1] ; 
			lazyMsk = new long [N << 1] ; 
			
			Arrays.fill(sTree, 1);
			Arrays.fill(lazy, 1);
			
			build(1,1,N);
		}
		
		void build(int node, int b, int e)	
		{
			if(b == e)		
			{
				sTree[node] = array[b];
				msk[node] = getMsk[array[b]] ; 
			}
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = mult(sTree[node<<1],sTree[node<<1|1]);
				msk[node] = msk[node<<1] | msk[node << 1 | 1];
			}
		}
		
		void update_range(int i, int j, int val)		
		{
			update_range(1,1,N,i,j,val);
		}
		
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				sTree[node] = mult(sTree[node] ,  modPow(val , (e-b+1)));			
				lazy[node] = mult(lazy[node] , val);
				msk[node] |= getMsk[val] ; 
				lazyMsk[node] |= getMsk[val] ;  	
			}							
			else		
			{
				int mid = b + e >> 1;
				propagateMult(node, b, mid, e);
				propagateMsk(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = mult(sTree[node<<1] , sTree[node<<1|1]);
				msk[node] = msk[node << 1] | msk[node << 1 | 1] ; 
			}
			
		}
		void propagateMult(int node, int b, int mid, int e)		
		{
			lazy[node<<1] = mult(lazy[node] , lazy[node << 1]);
			lazy[node<<1|1] = mult(lazy[node] , lazy[node << 1 | 1]);
			sTree[node<<1] = mult(sTree[node << 1] , modPow(lazy[node] , mid-b+1));	
			sTree[node<<1|1] = mult(sTree[node << 1| 1] , modPow(lazy[node] , e-mid));	
			
			lazy[node] = 1;
		}
		void propagateMsk(int node, int b, int mid, int e)		
		{
			msk[node << 1 ] |= lazyMsk[node] ; 
			msk[node << 1 | 1] |= lazyMsk[node] ; 
			lazyMsk[node << 1 ] |= lazyMsk[node] ; 
			lazyMsk[node << 1 | 1] |= lazyMsk[node] ; 
			
			lazyMsk[node] = 0 ;
		}
		
		int query(int i, int j)
		{
			return phi(queryMult(1,1,N,i,j) , queryMsk(1, 1, N, i, j));
		}
		
		int queryMult(int node, int b, int e, int i, int j)
		{
			if(i>e || j <b)
				return 1;		
			if(b>= i && e <= j)
				return sTree[node];
			
			int mid = b + e >> 1;
			propagateMult(node, b, mid, e);
			
			int q1 = queryMult(node<<1,b,mid,i,j);
			int q2 = queryMult(node<<1|1,mid+1,e,i,j);
			return mult(q1 , q2);	
		}
		long queryMsk(int node , int b , int e , int i , int j)
		{
			if(i>e || j <b)
				return 0;		
			
			if(b>= i && e <= j)
				return msk[node];
			
			int mid = b + e >> 1;
			propagateMsk(node, b, mid, e);
			
			long q1 = queryMsk(node<<1,b,mid,i,j);
			long q2 = queryMsk(node<<1|1,mid+1,e,i,j);
			return q1 | q2;
		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

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

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}