## Coprime Products

Time Limit: 1 sec
Memory Limit: 756 MB
Attempts: 45
Accuracy: 4.44%
Author: Akashdeep Goel

Adkroxx comes across another challenge. He's given an array of n integers and a number k. He is interested in finding the number of subsequences of the given array such that the product of numbers in the subsequence is a divisor of k and the elements of the subsequence are pairwise coprime.

Input:

First line of input contains space separated integers n and k.

The next line contains n space separated integers denoting the elements of the array.

Output:

Print the number of subsequences of the given array such that the product of numbers in the subsequence is a divisor of k and the elements of the subsequence are pairwise coprime. The product of numbers in empty subsequence is considered to be 1. Print the answer modulo 10^9+7.

Sample Input:

3 8

1 2 4

Sample Output:

6

Sample Explanation:

Required subsequences are {},{1},{2},{4},{1,2},{1,4}. Note that {2,4} is not counted as 2 and 4 are not coprime.

Constraints:

1<=n<=1000

1<=k<=10^9

1<=array elements<=10^9

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

4 years ago

cpp

0.00 sec

0 KB

4 years ago

cpp14

0.00 sec

0 KB

4 years ago

cpp14

0.07 sec

64 KB

4 years ago

cpp

0.07 sec

64 KB

4 years ago

cpp14

0.07 sec

64 KB