Bạn được cho hai số nguyên n và k. Nhiệm vụ của bạn là đếm số lượng mảng a1, a2, ..., an gồm các số nguyên dương sao cho:

LCM(~a_i~, ~a_{i+1}~) = k với mọi 1 ≤ i < n

Trong đó:

• LCM(x, y) là bội chung nhỏ nhất của x và y.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên t — số lượng bộ test.

• Mỗi dòng tiếp theo chứa hai số nguyên n và k:

  • n: độ dài của mảng.

  • k: giá trị yêu cầu của LCM.

Dữ liệu ra:

In ra t số nguyên — kết quả cho từng test case, modulo 10^9 + 7.

Ràng buộc:

~1 ≤ t ≤ 1000~

~2 ≤ n ≤ 10^9~

~1 ≤ k ≤ 10^9~

Ví dụ :

Input:

3
3 4
4 6
1337 42

Output:

11
64
602746233

Giải thích:

Test case 1: n = 3, k = 4 Ta cần đếm số mảng [a1, a2, a3] sao cho: LCM(a1, a2) = 4 và LCM(a2, a3) = 4

Các mảng hợp lệ: [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] [4, 4, 4] => Có 11 mảng hợp lệ.