Counting LCM Arrays

题目描述

给定两个整数 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：数组的长度和最小公倍数的值。

输出格式

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

3
3 4
4 6
1337 42

11
64
602746233

提示

$1 \le t \le 1000$ $2 \le n \le 10^9$ $1 \le k \le 10^9$ 样例解释：第一个测试用例的数组为 [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]。

标签: CSES3169|附加题1

来源

CSES3169|附加题1