시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 108 41 35 38.889%

문제

얼마 전 dp를 공부하던 택희는 엄청난 사실을 알아냈다.

피보나치 수는 엄청나게 빠르게 증가한다는 것이다.

택희는 피보나치 수열에 엄청나게 매료되어 100만 번째 피보나치 수까지 종이에 적었다. 하지만 적는 도중 택희는 느꼈다. 피보나치 수 정도로는 엄청난 택희를 만족시켜줄 수가 없었다.

택희는 더 엄청나게 빨리 증가하는 수열이 없을까 생각하다가, 아래와 같은 엄청난 수열을 생각해냈다.

$$ a_1 = k $$

$$ N_n =\left\{ 1, 2, 3, 4, …, n \right\} 일 때, a_{n+1} = \sum_{S \subset N_n} \sum_{i \in S} a_i $$

즉, an은 a1부터 an-1까지의 수 중 하나 이상을 뽑아 만들 수 있는 모든 부분집합의 합으로 정의하였다.

예를 들어 a1 = 1인 수열의 첫 몇 개 항을 살펴보면,

  • a2 = a1 = 1
  • a3 = (a1) + (a2) + (a1 + a2) = 4
  • a4 = (a1) + (a2) + (a3) + (a1 + a2) + (a1 + a3) + (a2 + a3) + (a1 + a2 + a3) = 24

와 같다.

택희는 이 엄청난 수열이 피보나치 수열보다 더 빨리 증가한다는 사실을 증명했고, 이제 이 수를 종이에 적기 시작했다.

100만 번째 수를 적었을 때쯤, 택희는 궁금한 것이 여러 가지 생겼다.

예를 들어, ai와 aj의 최대공약수는 얼마인지, ak의 값은 무엇인지, 수열에서 연속된 일부를 뽑아 더하면 얼마인지, 만일 수열의 첫 항 a1이 바뀌면 이 값들은 어떻게 바뀌는지 등, 자신이 만든 엄청난 수열에 대해 점점 궁금한 것이 많아진 택희는 이를 빠르게 계산해 줄 프로그램이 필요하다고 판단했다.

택희를 위해 택희의 궁금증을 해결해 줄 프로그램을 작성해 보자.

입력

첫 줄에 택희의 질문의 개수 Q가 주어진다. (1 ≤ Q ≤ 200000)

이어 Q줄에 걸쳐, 다음의 네 가지 타입 중 하나의 쿼리가 주어진다.

  • 1 a1 i j (1 ≤ a1 ≤ 105, 1 ≤ i, j ≤ 106): 첫 항이 a1인 엄청난 수열에서, ai와 aj의 최대공약수는?
  • 2 a1 i j (1 ≤ a1 ≤ 105, 1 ≤ i, j ≤ 106): 첫 항이 a1인 엄청난 수열에서, ai와 aj의 최소공배수는?
    • 단, 이 값은 너무 클 수 있으므로, 이 값을 L이라 할 때, $ \frac{L}{2^P} $이 정수가 되게 하는 가장 큰 정수 P만 구해보자.
  • 3 a1 i j (1 ≤ a1 ≤ 105, 1 ≤ i, j ≤ 106): 첫 항이 a1인 엄청난 수열에서, $ \sum_{k=i}^j a_k $는?
  • 4 a1 k (1 ≤ a1 ≤ 105, 1 ≤ k ≤ 106): 첫 항이 a1인 엄청난 수열에서, ak는?

3번 쿼리의 경우, 항상 i ≤ j를 만족하도록 입력이 주어진다.

출력

Q줄에 걸쳐, 각 쿼리에 대한 답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5
1 1 3 4
2 2 3 4
3 1 2 3
4 1 5
4 2 1000

예제 출력 1

4
4
5
240
949550777

힌트