Șogard is in huge trouble after his 9-day vacation. He is in urgent need of improving his mathematics skills for his upcoming math exam, so he calls his best friend Richard for some help. Richard came up with the following training routine: he has a chalkboard with the number $x$ written on it ($x$ is initially equal to $1$), and he will give $q$ queries of the following $3$ types:

• Replace $x$ with ($x$ multiplied by $a$), where $a$ is given.
• Replace $x$ with ($x$ divided by $a$), where $a$ is given such that it is $a$ divisor of $x$.
• You are given an interval $[ l, r ]$. Find how many numbers $d$ exist such that $d$ divides $x$, and the prime factors of $d$ are in the closed interval $[ l, r ]$. You need to find the answer modulo $10^{9} + 7$.

Task

Richard prepared the queries in advance, but he forgot to prepare the answers for his queries, and as such, he asks you for help in finding the answers to his queries so that he can help Șogard pass his upcoming math exam.

Input data

The first line of the input will contain the number $q$. The following $q$ lines will contain one of the following:

• A number $t$ which represents the type of query given.
• If $t = 1$, then on the same line, a new number $a$ which represents that $x$ will be multiplied by $a$.
• If $t = 2$, then on the same line, a new number $a$ which represents that $x$ will be divided by $a$. It is guaranteed that number $a$ will divide $x$.
• If $t = 3$, then on the same line, two new numbers $l, r$ which represent the interval for the 3rd type of query.

Output data

Print the answer for the 3rd type of queries, in the input order. Note that we want to find each answer modulo $10^{9} + 7$.

Constraints and clarifications

• $1 \leq q \leq 2 \cdot 10^{5}$
• $1 \leq a \leq 10^{6}$
• $1 \leq l \leq r \leq 10^{6}$

Example

stdin

12
1 5
1 10
1 15
1 9
3 2 3
3 2 5
3 3 5
1 49
1 11
3 5 16
2 77
3 4 16

stdout

8
32
16
24
8

Explanation

For the first query of the 3rd type, the prime decomposition of $x$ is $2 \times 3 \times 3 \times 3 \times 5 \times 5 \times 5$, so we can choose the $d$ in $8$, $32$, respectively $16$ ways. Then, for the next queries of the 3rd type, our $x$ is multiplied by $7 \times 7 \times 11$, so we can choose $d$ in $24$ ways, respectively $8$ ways.