The Enormous Sequence

Fibonacci numbers grow fast. Taekhee wrote them on paper all the way to the millionth term and still was not satisfied, so he defined a sequence of his own that grows much faster.

The first term is $a_1 = k$. With $N_n = \{1, 2, 3, \dots, n\}$, the next term is given by

$a_{n+1} = \sum_{\emptyset \ne S \subseteq N_n} \sum_{i \in S} a_i$

In other words, for every way of choosing at least one term among $a_1$ through $a_n$, take the sum of the chosen terms, and $a_{n+1}$ is the total of all those sums.

For $a_1 = 1$ the first few terms are

• $a_2 = (a_1) = 1$
• $a_3 = (a_1) + (a_2) + (a_1 + a_2) = 4$
• $a_4 = (a_1) + (a_2) + (a_3) + (a_1 + a_2) + (a_1 + a_3) + (a_2 + a_3) + (a_1 + a_2 + a_3) = 24$

Taekhee prepared $Q$ questions about this sequence. Each question comes with its own first term $a_1$, so each question is about its own sequence. Write a program that answers all of them.

The first line contains the number of questions $Q$. ($1 \le Q \le 200000$)

Each of the next $Q$ lines contains one question in one of the four forms below.

• 1 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): in the sequence whose first term is $a_1$, what is the greatest common divisor of $a_i$ and $a_j$?
• 2 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): in the sequence whose first term is $a_1$, let $L$ be the least common multiple of $a_i$ and $a_j$. That value is far too large, so the question asks for the largest integer $P$ such that $\frac{L}{2^P}$ is an integer.
• 3 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): in the sequence whose first term is $a_1$, what is $\sum_{k=i}^{j} a_k$? A question of this form always satisfies $i \le j$.
• 4 a1 k ($1 \le a_1 \le 10^5$, $1 \le k \le 10^6$): in the sequence whose first term is $a_1$, what is $a_k$?

Print $Q$ lines. On each line print the answer to the corresponding question modulo 1,000,000,007, in the order the questions are given.