SOLVE
LATER
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
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
In the sample test case, here's a list of some of the special subsets: \([5, 16], [20], [5, 20], [16, 20]\) and \([5, 16, 20]\).