Composite Facts

Let's define two functions F and S:

• F(n) = 1 + n!
• S(n,m) = Sum of first m non-prime integers which are greater than n

Here n! represents the factorial of n.

You are given N integers A1, A2, A3, ..., AN and Q queries. There are two types of queries:

• 1 P X which means that AP is now equal to X.
• 2 L R which means that you have to print the sum of all S(F(Ai),Ai-1) such that L ≤ i ≤ R.

You have to process all of Q queries. Since the answer to the queries of the second type can be too large, you will have to print the answer modulo 109+7.

Input

The first line of the input contains two integers N and Q (1≤ N,Q ≤ 105) where N is the number of given integers and Q is the number of queries.

The second line of the input contains N space-separated integers A1, A2, A3, ..., AN (2 ≤ Ai ≤ 106).

Each of the next Q lines of the input will contain a query of the form 1 P X or 2 L R (1≤ P,L,R ≤ 105, 2 ≤ X ≤ 106, 1 ≤ L ≤ R ≤ N).

Output

Print the answer of each query of the second type in a single line.

Sample

8 5
13 44 28 15 36 71 55 93
2 3 6
1 5 63
2 4 8
1 8 17
2 1 8

802241191
770652191
774742353