N Slovakistan farmers own neighbouring fields alongside a river, forming a straight line. Each field is infested with (possibly zero) pests.

Thanks to ingenious Slovakistan science, each species of pest can be assigned a prime number. Each field can then be assigned a positive number, representative of the pests that are infesting it - the prime factorization of this number indicates which pests are present, with the powers of each prime number representing how strongly the field is infested with that pest.

Every pesticide can then be assigned a positive number, which is designed in such a way that its prime factorization indicates what pests it can supress, with the powers of each prime number representing how strong infestations of that pest it is able to handle.

To aid their farmers, the government of Slovakistan can select a pest, and then pump a pesticide designed specifically against it into the river, completely supressing that species on all fields. However, due to environmental concerns, they will only use one pesticide at a time - when the government switches to a different pesticide, designed against a different pest, the ones previously supressed return to all fields in full force.

On top of that, the farmers union can request pesticide to be sprayed on the fields themselves. Since this is done using an airplane, they can only request pesticide to be sprayed on a contiguous segment of fields.

Pesticides with higher numbers are more expensive. Now, for each request the government would like to know the cheapest pesticide they can use to supress all pests on all the fields in the requested segment.

Input

The first line contains two integers 1 ≤ N ≤ 50000 and 1 ≤ Q  ≤ 10⁵ - the number of fields and the number of events.

The second line contains N integers f₁, ..., f_N - the numbers assigned to the fields. They will be positive and not greater than 10⁵.

Q lines follow, describing events in the order in which they happened. Each event is either of the form 0 L R or 1 P.

If the event is of the form 1 P, 1 ≤ P ≤ 10⁵, it means that the government of Slovakistan began pumping pesticide against the pest number P (a prime number) into the river, and are no longer pumping pesticide against the previous pest, if they were doing so. The exception is P = 1, meaning that there is simply no pesticide being pumped into the river. In the beginning, the government is not pumping any pesticide.

If the event is of the form 0 L R, 1 ≤ L ≤ R ≤ N, it means that the farmers requested pesticide to be sprayed on the contiguous segment of fields from the L-th to the R-th, inclusive.

Output

For each event of form 0 L R, output the smallest number of pesticide which can handle all infestations on the segment of fields from L to R, modulo 10⁹+7, taking into account that some pests may be supressed due to the government's aid. More formally, output the least common multiple of the numbers f_L, ..., f_R, after they have had all factors of P from the last 1 P event removed, modulo 10⁹+7.

Example

Input:
10 12
4 2 3 5 6 47 10007 32768 59049 1
0 1 5
0 2 5
1 2
0 1 5
0 2 5
0 6 10
1 3
0 6 10
1 1
0 1 10
0 10 10
0 1 5

Output:
60
30
15
15
772456932
411740567
342852967
1
60