엄청난 수열

피보나치 수는 빠르게 커진다. 택희는 100만 번째 피보나치 수까지 종이에 적어 보고도 성에 차지 않아, 훨씬 빠르게 커지는 수열을 직접 정의했다.

첫 항은 $a_1 = k$이고, $N_n = \{1, 2, 3, \dots, n\}$이라 할 때 다음 항은 아래 식으로 정해진다.

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

즉 $a_{n+1}$은 $a_1$부터 $a_n$까지 중에서 하나 이상을 고르는 모든 방법마다 고른 수의 합을 구한 다음, 그 값을 전부 더한 것이다.

$a_1 = 1$인 수열의 앞부분 몇 항은 이렇다.

• $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$

택희는 이 수열을 놓고 질문 $Q$개를 준비했다. 질문마다 첫 항 $a_1$을 따로 주므로 질문마다 다른 수열을 다룬다. 모든 질문에 답하는 프로그램을 작성하자.

첫 줄에 질문의 개수 $Q$가 주어진다. ($1 \le Q \le 200000$)

이어지는 $Q$개의 줄에 다음 네 가지 중 한 형태의 질문이 주어진다.

• 1 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): 첫 항이 $a_1$인 수열에서 $a_i$와 $a_j$의 최대공약수는 얼마인가?
• 2 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): 첫 항이 $a_1$인 수열에서 $a_i$와 $a_j$의 최소공배수를 $L$이라 하자. 이 값은 너무 크므로, $\frac{L}{2^P}$이 정수가 되게 하는 가장 큰 정수 $P$를 묻는다.
• 3 a1 i j ($1 \le a_1 \le 10^5$, $1 \le i, j \le 10^6$): 첫 항이 $a_1$인 수열에서 $\sum_{k=i}^{j} a_k$는 얼마인가? 이 형태의 질문은 항상 $i \le j$를 만족하도록 주어진다.
• 4 a1 k ($1 \le a_1 \le 10^5$, $1 \le k \le 10^6$): 첫 항이 $a_1$인 수열에서 $a_k$는 얼마인가?

$Q$개의 줄에 걸쳐 각 질문의 답을 1,000,000,007로 나눈 나머지를 입력에 주어진 순서대로 출력한다.