First factorize \(M\). It could be done in \(O(\sqrt M)\) using trial division, or \(O(\sqrt[4]M)\) using more advanced techniques like Pollard’s rho. Let \(M = p_1^{k_1} p_2^{k_2} ... p_w^{k_w}\) be its prime factorization.

Then, for each \(A_i\), we could note that if \(A_i\) doesn’t divide \(M\), such \(A_i\) could never be part of a good subsequence, so we may ignore them hereafter. We could quickly factorize the remaining \(A_i\), as its prime factors must be a subset of the prime factors of \(M\). This takes \(O(N \log M)\) time.

Note that if we identify each number with the multiset of its prime factorization, the LCM of a sequence of numbers is the multiset union of its elements. Thus the condition for a good subsequence could be rephrased as: for each prime factor \(p_j\), at least one element in the sequence must have its exponent equal \(k_j\); that is, it matches the multiplicity of that prime factor in \(M\).

We could thus reduce the problem in terms of bitmasks: for each remaining \(A_i\), let’s define \(b_i\) to be a bitmask consisting of \(w\) bits, where the \(j\)-th bit is \(1\) iff the multiplicity of the prime factor \(p_j\) in \(A_i\) is \(k_j\). The problem then becomes counting the number of subsequences of \(b\) whose bitwise-or is \(1\) in all \(w\) bits.

This is difficult to do directly, but can be done using the Inclusion–exclusion principle.

In general, principle of inclusion-exclusion (PIE) can be summarized with the following steps:

1. Identify a set of “violations”, i.e. a set of rules you want to obey and specific requirements for each rule to be broken.
2. Identify a way to calculate \(F(S)\): for every subset \(S\) of possible violations, the number of ways to violate at least that subset (note that we don’t need to know how to calculate the number of ways to violate exactly that subset).
3. The number of ways to obey all rules (i.e. not commit any violations) will then equal \((\sum _ {|S| \text{ is even}}F(S)) - (\sum _ {|S| \text{ is odd}}F(S)) = \sum _ S (-1) ^ {|S|} \cdot F(S)\) (note that zero is also even)

In this case, there is a set of \(w\) violations, that is, violation \(i\) is when none of the elements of the subsequence have a \(1\)-bit in the \(i\)-th position. Thus \(F(S)\) can be easily calculated; if there are \(x_S\) elements in \(b\) that have \(0\)-bits in all the positions of \(S\), then the number of non-empty subsequences with those violations is \(F(S) = 2^{x_S} - 1\). You can find all \(x_S\) by first collecting the frequency of each mask in \(b\), then propagating those frequencies to its supermasks via fast zeta transform / sum-over-subsets. This will thus take \(O(w \cdot 2^w)\) time; note \(w \leq 13\) for the constraints of this problem.

Note that if you use \(F(S) = 2^{x_S}\) instead (counting the empty subsequence too), you may need to specially handle the case where \(M = 1\), where the empty subsequence could be accidentally counted.