Count special subsets
Tag(s):

## Dynamic programming, Integer factorization, Mathematics, Medium, Number Theory

Problem
Editorial
Analytics

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$

SAMPLE INPUT
1
5 10
5 9 16 20 25

SAMPLE OUTPUT
11

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HourStorm #6

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures