SOLVE

LATER

Count special subsets

/

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\)

Explanation

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]\).

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...