Subsequences counting - MarisaOJ: Marisa Online Judge

Subsequences counting

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $A$ containing $n$ primes, find the number of non-empty subsequences whose least common multiple (LCM) is less than or equal to a given value $k$. ### Input - The first line contains 2 integers $n, k$. - The second line contains $n$ primes $A_i$. ### Output - Print the number of subsequences, modulo $10^9+7$. ### Constraints - $1 \le n \le 1000$. - $1 \le A_i \le 50$. - $1 \le k \le 10^{18}$ ### Example Input: ``` 3 16 2 3 5 ``` Output: ``` 6 ```