Background

Before Kirito and Eugeo went with Alice to the Northern Cave, Eugeo could only chop the Demon Tree—Gigas Cedar—every day with the Dragon Bone Axe...

Please ignore bilibili’s watermark.

Problem Description

Kirito and Eugeo felt bored chopping trees every day, so they started competing to see who could produce more “good sounds” while chopping. Gradually, they found this was still not interesting, so they changed the rules a bit based on that:

Before each person chops the tree, they will randomly get a sequence $s_1, s_2, \dots, s_n$ of length $n$. At the beginning, everyone’s score is $1$. When a “good sound” occurs on the $i$-th chop, the score becomes the least common multiple of the original score and $s_i$, which is commonly called ${\rm lcm}$.

Now Kirito has obtained a sequence $s_1, s_2, \ldots, s_n$ of length $n$. He wants to know his expected score if the probability of getting a “good sound” on each chop is $50\%$.

Since Kirito does not want to see decimals, please tell Kirito the value of the answer multiplied by $2^n$ modulo $p$.

Input Format

There are $2$ lines in total.

The $1$-st line contains $2$ positive integers $n$ and $p$, representing the length of the sequence and the given modulus. It is guaranteed that the modulus is a prime number.

The $2$-nd line contains $n$ positive integers. 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$.

3 998244353
1 2 3

24

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

516032

Hint

Sample Explanation 1

There are $8$ possible cases in total:

• No “good sound” occurs, the score is $1$, and the probability is $\frac{1}{8}$.

• Only the first time has a “good sound”, the score is $1$, and the probability is $\frac{1}{8}$.

• Only the second time has a “good sound”, the score is $2$, and the probability is $\frac{1}{8}$.

• Only the third time has a “good sound”, the score is $3$, and the probability is $\frac{1}{8}$.

• Only the third time does not have a “good sound”, the score is $\operatorname{lcm}(1, 2)=2$, and the probability is $\frac{1}{8}$.

• Only the second time does not have a “good sound”, the score is $\operatorname{lcm}(1, 3)=3$, and the probability is $\frac{1}{8}$.

• Only the first time does not have a “good sound”, the score is $\operatorname{lcm}(2, 3)=6$, and the probability is $\frac{1}{8}$.

• Every time produces a “good sound”, the score is $\operatorname{lcm}(1, 2, 3)=6$, and the probability is $\frac{1}{8}$.

So 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$.

After multiplying by $2^3$, the answer is $24$.

Subtasks

This problem uses bundled test.

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, and $1\leq s_i\leq 300$.

This problem has $7$ subtasks. The score and constraints of each subtask are as follows:

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

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

Subtask $3$ ($10$ points): $n=100$, and the number of distinct positive integers in $s$ is at most $18$.

Subtask $4$ ($20$ points): $n=100$, and there do not exist $1\leq i \neq j \leq n$ such that $s_i=s_j$. It is also guaranteed that the testdata is 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 constraints.

This problem is dedicated to celebrating the 10th anniversary of Sword Art Online. Seems like it is a few months late...

Source

MtOI2019 Extra Round T4

Problem setter: CYJian.

Problem reviewer: suwAKow.

Translated by ChatGPT 5