Bob fell in love with LCM and GCD. So much that he started seeing LCMs and GCDs everywhere. Betty, his girlfriend was jealous and she gave Bob an array A[ ] of integers, which had nothing to do with LCMs or GCDs.

Quickly, naughty Bob evaluated a new array B[ ] containing n integers, such that B[i] is LCM(1, 2, 3 ... A[i]), A[i]>0. When A[i] is 0, B[i] is also 0.

Angry Betty decided to give m queries to Bob, each being one of the following type:

• "0 i j p", meaning add 'p' to each element in A[i...j]. -300000 <= p <= 300000, 0 <= i <= j < n
• "1 i j", meaning print the LCM of all elements in B[i...j]. 0 <= i <= j < n
• "2 i j", meaning print the GCD of all elements in B[i...j]. 0 <= i <= j < n

Input

First line contains n (n <= 100000) and m (m <= 35000).

Second line contains n integers in the original array A[ ].

Next m lines contain one of the above said queries.

It is guaranteed that A[i] after any number of updates will satisfy 0 <= A[i] <= 300000.

Output

Output one line for each query of type 1 or 2, modulo 1000000007.

Example

Input:
5 5
4 1 3 6 2
1 2 4
2 1 3
0 0 3 2
1 1 2
2 2 4

Output:
60
1
60
2