Learning is light, not learning is darkness

Lately Alf has done nothing at all. He has not even broken anything in the past week. Linn decided it was time he stopped idling and started studying.

Linn chose a simple problem to start with. You are given an array of positive integers. Two kinds of operations are performed on the array:

• 0 i x: assign the value $x$ to the $i$-th element of the array.
• 1 l r: output the number of divisors of the product of the numbers on the segment from $l$ to $r$. This number can be very large, so output the answer modulo $10^9+7$.

Alf is secretly in love with Linn, so he cannot refuse her. He does not want to do the work, though. So he asked you to write a program that solves this problem without Linn finding out.

The first line contains the number $n$ ($1 \le n \le 5 \cdot 10^4$), the number of elements in the array.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$), the elements of the array.

The third line contains the number $q$ ($1 \le q \le 10^4$), the number of queries.

Each of the next $q$ lines contains three integers. If the first integer is 0, the query updates an array element. If the first integer is 1, the query asks for the number of divisors of the product on a segment.

It is guaranteed that in every query $1 \le i, l, r \le n$ and $1 \le x \le 10^4$.

For each query of type 1, output on its own line the number of divisors of the product of all numbers on the given segment, modulo $10^9+7$.