You are given an array \(a\) of \(n\) integers and another integer \(x\). You need to determine the number of special subsets of those \(n\) integers. If a subset is not empty and the resultant score of that subset is equal to \(x\), then that subset is called a special subset.
Consider a number \(s\) that is equal to the product of all the integers in a subset. The resultant score of that subset is the product of all the distinct prime numbers that divide the number \(s\).
For example, let us consider that \(a = [5, 9, 16, 20, 25]\) and \(x = 10\). Consider the subset \([5, 16, 20]\). The product of all the integers in this subset is \(s = 1600\). The prime numbers that divide this number \(s\) are \(2\) and \(5\). So the resultant score of this subset is \(2*5 = 10\). As this score is equal to \(x\) ,therefore, the selected subset is considered as a special subset.
Input format
- First line: A single integer \(t\) that denotes the number of test cases
- For each test case:
- First line: Two integers \(n\) and \(x\)
- Next line: \(n\) space-separated integers of the array \(a\)
Output format
For each test case, print a single integer representing the number of special subsets of the given array. Since the answer can be very large, print it modulo \(10^9+7\).
Input Constraints
- \(1 \le t \le 5\)
- \(1 \le n \le 50000\)
- \(1 \le a_i \le 10^6\)
- \(2 \le x \le 10^6\)