Subsequences counting - MarisaOJ: Marisa Online Judge

Given an array

A

$A$ containing

n

$n$ primes, find the number of non-empty subsequences whose least common multiple (LCM) is less than or equal to a given value

k

$k$ . ### Input - The first line contains 2 integers

n, k

$n, k$ . - The second line contains

n

$n$ primes

A_{i}

$A_i$ . ### Output - Print the number of subsequences, modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

1 \leq n \leq 1000

$1 \le n \le 1000$ . -

1 \leq A_{i} \leq 50

$1 \le A_i \le 50$ . -

1 \leq k \leq 10^{18}

$1 \le k \le 10^{18}$ ### Example Input:

316235

$3 16 2 3 5$

Output:

6

$6$

Bitmask DP
	Binary board
	Travelling Salesman Problem 2
	Brewing potion 5
	Subsequences counting
	Wooden house
	Xiangqi
	Packing
	Permutation counting
	Counting tilings
	Superstring
	Custom keyboard
	Mushroom harvesting III

Topic

Math

Dynamic Programming

Bitmasks

Rating

1400

Solution (0)

Solution