Problem Background

Before Kirito and Eugeo set off with Alice for the Northern Cave, Eugeo could only use his dragonbone axe to chop the demon tree—Gigas Cedar...

Please ignore the bilibili watermark

Problem Description

Kirito and Eugeo found chopping trees every day to be monotonous, so they started competing to see who could produce more pleasing sounds while chopping. Eventually, they realized even this was uninteresting, so they made a slight modification to the game:

Each person would randomly receive a sequence of length $n$, denoted as $s_1, s_2, \dots, s_n$. Initially, each person's score is $1$. When the $i$-th chop produces a pleasing sound, the score becomes the least common multiple (LCM) of the current score and $s_i$.

Now, Kirito has received a sequence of length $n$, $s_1, s_2, \ldots, s_n$. He wants to know the expected score when the probability of producing a pleasing sound each time is $50\%$.

Since Kirito dislikes decimal numbers, please tell him the answer multiplied by $2^n$ modulo $p$.

Input Format

There are $2$ lines in total.

The first line contains $2$ positive integers $n$ and $p$, representing the length of the sequence and the given modulus, respectively. Ensure that the modulus is a prime number.

The second line contains $n$ positive integers, where the $i$-th number represents $s_i$.

Output Format

There is $1$ line in total, containing $1$ positive integer, representing the expected score multiplied by $2^n$ modulo $p$.

Sample Input and Output

Sample Input #1

3 998244353
1 2 3

Sample Output #1

24

Sample Input #2

10 998244353
1 2 3 4 5 6 7 8 9 10

Sample Output #2

516032

Notes

Sample Explanation 1

There are $8$ possible scenarios:

• No pleasing sounds occur, the score is $1$, with a probability of $\frac{1}{8}$.
• Only the first chop produces a pleasing sound, the score is $1$, with a probability of $\frac{1}{8}$.
• Only the second chop produces a pleasing sound, the score is $2$, with a probability of $\frac{1}{8}$.
• Only the third chop produces a pleasing sound, the score is $3$, with a probability of $\frac{1}{8}$.
• Only the third chop does not produce a pleasing sound, the score is $\operatorname{lcm}(1, 2)=2$, with a probability of $\frac{1}{8}$.
• Only the second chop does not produce a pleasing sound, the score is $\operatorname{lcm}(1, 3)=3$, with a probability of $\frac{1}{8}$.
• Only the first chop does not produce a pleasing sound, the score is $\operatorname{lcm}(2, 3)=6$, with a probability of $\frac{1}{8}$.
• Every chop produces a pleasing sound, the score is $\operatorname{lcm}(1, 2, 3)=6$, with a probability of $\frac{1}{8}$.

Thus, the expected value is $\frac{1}{8}+\frac{1}{8}+\frac{2}{8}+\frac{3}{8}+\frac{2}{8}+\frac{3}{8}+\frac{6}{8}+\frac{6}{8}=3$.

Multiplying by $2^3$ gives the answer $24$.

Subtasks

This problem uses bundled testing.

For $100\%$ of the data, $1 \leq n \leq 3 \times 10^5$, $10^7 \leq p \leq 1.1 \times 10^9$ and $p$ is a prime number, $1 \leq s_i \leq 300$.

There are $7$ subtasks, each with its own score and constraints:

Subtask $1$ ($3$ points): $n=1$.

Subtask $2$ ($7$ points): $n=18$.

Subtask $3$ ($10$ points): $n=100$, with no more than $18$ distinct positive integers in $s$.

Subtask $4$ ($20$ points): $n=100$, with no $1 \leq i \neq j \leq n$ such that $s_i = s_j$, and the data is guaranteed to be random.

Subtask $5$ ($20$ points): $1 \leq s_1, s_2, \ldots, s_n \leq 100$.

Subtask $6$ ($20$ points): $1 \leq n \leq 10^4$.

Subtask $7$ ($20$ points): No special restrictions.

This problem is dedicated to the 10th anniversary of Sword Art Online. It seems to be a few months late...

Problem Source

MtOI2019 Extra Round T4

Problem Author: CYJian

Problem Tester: suwAKow

见题面 Input 部分

见题面 Output 部分