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
| Input | Output |
|---|---|
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 |
