Given two integers $n$ and $k$ , your task is to count the number of arrays $a_1, a_2,\dots, a_n$ of positive integers where $\operatorname{lcm}(a_i, a_{i+1}) = k$ for all $1 \le i < n$ .
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.
Print $t$ integers: the answer to each test case modulo $10^9 + 7$ .
3 3 4 4 6 1337 42\n · \n · \n · \n
11 64 602746233\n \n \n
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]$ .