Kirito and Eugeo's LCM Challenge

Kirito and Eugeo are bored with their daily tree cutting routine and decided to spice things up by competing over who can generate more 'good sounds' while cutting trees. Initially, each player starts with a score of \(1\). Before cutting the trees, each player is randomly given a sequence of \(n\) integers \(s_1, s_2, \dots, s_n\). Every time a player produces a good sound (which happens independently with a probability of \(50\%\) per attempt), their current score is updated to the least common multiple (\(\mathrm{lcm}\)) of their current score and the corresponding number in the sequence. In other words, if at the \(i\)-th attempt a good sound is achieved, the score becomes:

\[ \text{score} = \mathrm{lcm}(\text{score}, s_i) = \frac{\text{score} \times s_i}{\gcd(\text{score}, s_i)} \]

After all \(n\) attempts, let \(S\) be any subset of indices \(\{1,2,\dots,n\}\) corresponding to the attempts with good sounds (with the convention that the \(\mathrm{lcm}\) of an empty set is \(1\)). The expected final score is

\[ E = \frac{1}{2^n} \sum_{S\subseteq\{1,2,\dots,n\}} \mathrm{lcm}(S), \]

but since Kirito dislikes fractions, you are asked to compute the value

\[ \left( \sum_{S\subseteq\{1,2,\dots,n\}} \mathrm{lcm}(S) \right) \bmod p \]

given the sequence \(s_1, s_2, \dots, s_n\) and a modulus \(p\).

inputFormat

The first line contains two integers \(n\) and \(p\) representing the number of elements and the modulus, respectively.

The second line contains \(n\) space-separated integers \(s_1, s_2, \dots, s_n\).

outputFormat

Output a single integer, which is the sum of the \(\mathrm{lcm}\) of all subsets (with the \(\mathrm{lcm}\) of an empty subset defined as \(1\)) modulo \(p\).

sample

3 100
2 3 4

44