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 PracticeIsFun {

	
	static int numPrimes,MOD=(int)1e9+7;
	static int[] primes;
	static long []pre;
	static int []inv;
	static boolean isPrime(int x) {
		for(int i=2;i*i<=x;i++)
			if(x%i==0)
				return false;
		return true;
	}
	static int modInverse(int x) {
		return inv[x];
	}
	static int pow(long b,int e) {
		long ans=1;
		while(e>0) {
			if(e%2==1) 
				ans=ans*b%MOD;
			b=b*b%MOD;
			e>>=1;
			
		}
		return (int)ans;
	}
	
	static int n,a[],MAX=305;
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		primes=new int[62];
		pre=new long [MAX];
		int last=0;
		for(int p=2;p<=300;p++)
			if(isPrime(p))
				primes[last++]=p;
		numPrimes=primes.length;
		inv=new int [MAX];
		inv[1] = 1;
		
		for(int i=1;i<=300;i++) {
			for(int j=0;j<numPrimes;j++) {
				if(i%primes[j]==0)
					pre[i]|=1L<<j;
			}
			if(i>1) {
				inv[i] = (int) ((MOD - (MOD/i) *1L* inv[MOD%i] % MOD));
				
			}
				
		}
		
	
		n=sc.nextInt();
		int q=sc.nextInt();
		a=new int [n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		
	
		SegmentTree tree=new SegmentTree();
		while(q-->0) {
			String t=sc.next();
			
			int l=sc.nextInt()-1,r=sc.nextInt()-1;
			if(t.equals("TOTIENT")) {
				out.println(tree.query(l, r));
			}
			else {
				int x=sc.nextInt();
				tree.updateRange(l, r, x);
			}
		}
		
		out.close();
	}
	static class SegmentTree{
		
		long []prod,msks,lazy,lazy2;
		SegmentTree(){
			int N=1;
			while(N<n)
				N<<=1;
			prod=new long [N<<1];
			msks=new long [N<<1];
			lazy=new long [N<<1];
			lazy2=new long [N<<1];
			build(1,0,n-1);
		}
		void updateNode(int node,int x,int tl,int tr) {
			
			int len=tr-tl+1;
			prod[node]=prod[node]*pow(x,len)%MOD;
			lazy[node]=lazy[node]*x%MOD;
			long tmp=pre[x];
			msks[node]|=tmp;
			lazy2[node]|=tmp;
		
			
		}
		void build(int node,int tl,int tr) {
			lazy[node]=prod[node]=1;
			if(tl==tr) {
				updateNode(node,a[tl],tl,tr);
				
			}
			else {
				int mid=tl+tr>>1,left=node<<1,right=left|1;
				build(left,tl,mid);
				build(right,mid+1,tr);
				merge(node);
			}
			
		}
		void merge(int node) {
			int left=node<<1,right=left|1;
			msks[node]=msks[left]|msks[right];
			prod[node]=prod[left]*prod[right]%MOD;
		}
		
		void updateRange(int l,int r,int x) {
			updateRange(1,0,n-1,l,r,x);
		}
		void updateRange(int node,int tl,int tr,int l,int r,int x) {
			if(tr<l || r<tl)
				return ;
			if(tl>=l && tr<=r) {
				updateNode(node, x, tl, tr);
			}
			else {
				int mid=tl+tr>>1,left=node<<1,right=left|1;
				propagate(node,tl,mid,tr);
				updateRange(left,tl,mid,l,r,x);
				updateRange(right,mid+1,tr,l,r,x);
				merge(node);
			}
		}
		long query(int l,int r) {
			long []x= query(1,0,n-1,l,r);
			long ans=x[0],msk=x[1];
			for(int i=0;i<numPrimes;i++) {
				if((msk & (1L<<i))==0)
					continue;
				int p=primes[i];
				
				ans=ans*(p-1)%MOD;
				ans=ans*modInverse(p)%MOD;
			}
			
			return ans;
		}
		long[] query(int node,int tl,int tr,int l,int r) {
			if(tr<l || r<tl)
				return new long [] {1,0};
			if(tl>=l && tr<=r) {
				return new long [] {prod[node],msks[node]};
			}
			else {
				int mid=tl+tr>>1,left=node<<1,right=left|1;
				propagate(node,tl,mid,tr);
				long []x1=query(left,tl,mid,l,r),x2=query(right,mid+1,tr,l,r);
				return new long [] {x1[0]*x2[0]%MOD,x1[1]|x2[1]};
				
			}
			
			
		}
		void propagate(int node,int tl,int  mid,int tr) {
			int left=node<<1,right=left|1;
			int len1=mid-tl+1,len2=tr-mid;
			long x=lazy[node];
			prod[left]*=pow(x,len1);
			prod[right]*=pow(x,len2);
			lazy[left]*=x;
			lazy[right]*=x;
			prod[left]%=MOD;
			prod[right]%=MOD;
			lazy[left]%=MOD;
			lazy[right]%=MOD;
			lazy[node]=1;
//			for(int i=0;i<numPrimes;i++) {
//				int p=primes[i];
//				if(x%p==0)
//				{
//					msks[left]|=1L<<i;
//					msks[right]|=1L<<i;
//				}
//			}
			x=lazy2[node];
			msks[left]|=x;
			msks[right]|=x;
			lazy2[left]|=x;
			lazy2[right]|=x;
			
		}
		
		
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

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

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

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

		String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}

}
