链接: https://cses.fi/problemset/task/3169

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定两个整数 $n$ 和 $k$，你的任务是统计满足以下条件的正整数数组 $a_1, a_2,\dots, a_n$ 的数量：对所有 $1 \le i < n$，都有 $\operatorname{lcm}(a_i, a_{i+1}) = k$。

输入

第一行包含一个整数 $t$：测试用例的数量。

接下来的 $t$ 行每行有两个整数 $n$ 和 $k$：数组的长度和 lcm 的值。

输出

输出 $t$ 个整数：每个测试用例的答案对 $10^9 + 7$ 取模的结果。

数据范围

$1 \le t \le 1000$ $2 \le n \le 10^9$ $1 \le k \le 10^9$

样例输入

3
3 4
4 6
1337 42

样例输出

11
64
602746233