给定 ，和一个数列 ，问你有多少种方案构造一个长度为 的序列 ，满足下的条件：
You are given two integers and and an array of integers. For each it holds that .
Your task is to count the number of different arrays of length such that:
Here denotes the greatest common divisor (GCD) of integers .
Since this number can be too large, print it modulo .
Each test consist of multiple test cases. The first line contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers and (, ) — the length of the array and the maximum possible value of the element.
The second line of each test case contains integers () — the elements of the array .
It is guaranteed that the sum of across all test cases doesn't exceed .
For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo .
5 3 5 4 2 1 2 1 1 1 5 50 2 3 5 2 3 4 1000000000 60 30 1 1 2 1000000000 1000000000 2
3 1 0 595458194 200000000
In the first test case, the possible arrays are:
In the second test case, the only array satisfying the demands is .
In the third test case, it can be proven no such array exists.