영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
Given two integers n and k, your task is to count the number of arrays a_1, a_2,…, a_n of positive integers where lcm(a_i, a_{i+1}) = k for all 1 ≤ i < n.
Input
The first line has an integer t: the number of test cases.
The next t lines have two integers n and k: the length of the array and the value of lcm.
Output
Print t integers: the answer to each test case modulo 10^9 + 7.
Constraints
- 1 ≤ t ≤ 1000
- 2 ≤ n ≤ 10^9
- 1 ≤ k ≤ 10^9
Example
Explanation: The arrays for the first test case are [1, 4, 1], [1, 4, 2], [1, 4, 4], [2, 4, 1], [2, 4, 2], [2, 4, 4], [4, 1, 4], [4, 2, 4], [4, 4, 1], [4, 4, 2] and [4, 4, 4].
예제
예제 1
3 3 4 4 6 1337 42
11 64 602746233