[MtOI2019] 恶魔之树

在 Kirito 和 Eugeo 还没有与 Alice 前往北之洞窟的时候，Eugeo 每天只能用龙骨斧砍恶魔之树——基家斯西达……  ~~请忽略bilibili的水印~~

Kirito 和 Eugeo 每天砍树觉得很无聊，于是开始比谁砍出好声音的次数多。渐渐地，他们发现这样也没有意思了，于是在这个基础上改了一点： 每个人去砍树前，会随机得到一个长度为 $n$ 的数列 $s_1, s_2, \dots, s_n$ 。最初每个人的得分都是 $1$，当第 $i$ 次砍出了一个好声音时，得分就变成了原来的得分与 $s_i$ 的最小公倍数，也就是常说的 ${\rm lcm}$。 现在 Kirito 已经得到了一个长度为 $n$ 的数列 $s_1, s_2, \ldots, s_n$ 。他想知道，如果每一次砍出好声音的概率是 $50\%$ 时他的期望得分。 由于 Kirito 不想看到小数，所以请你告诉 Kirito 答案乘 $2^n$ 对 $p$ 取模的值。

共 $2$ 行。 第 $1$ 行包含 $2$ 个正整数 $n$ 和 $p$ ，代表数列的长度和给定的模数。**保证模数为质数** 第 $2$ 行包含 $n$ 个正整数，第 $i$ 个数代表 $s_i$。

共 $1$ 行，包含 $1$ 个正整数，代表得分的期望值乘 $2^n$ 对 $p$ 取模的结果。

3 998244353
1 2 3

24

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

516032

#### 样例解释 1 一共有 $8$ 种情况： - 没有出现好声音，得分为 $1$，概率为 $\frac{1}{8}$。 - 只有第一次出现了好声音，得分为 $1$，概率为 $\frac{1}{8}$。 - 只有第二次出现了好声音，得分为 $2$，概率为 $\frac{1}{8}$。 - 只有第三次出现了好声音，得分为 $3$，概率为 $\frac{1}{8}$。 - 只有第三次没有出现好声音，得分为 $\operatorname{lcm}(1, 2)=2$，概率为 $\frac{1}{8}$。 - 只有第二次没有出现好声音，得分为 $\operatorname{lcm}(1, 3)=3$，概率为 $\frac{1}{8}$。 - 只有第一次没有出现好声音，得分为 $\operatorname{lcm}(2, 3)=6$，概率为 $\frac{1}{8}$。 - 每一次都砍出了好声音，得分为 $\operatorname{lcm}(1, 2, 3)=6$，概率为 $\frac{1}{8}$。 所以期望值为 $\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$ 乘上 $2^3$ 得到答案为 $24$。 ### 子任务 本题采用捆绑测试。 对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$10^7 \leq p \leq 1.1 \times 10^9$且$p$为质数，$1\leq s_i\leq 300$。 本题共 $7$ 个子任务，各子任务的分值和限制如下： 子任务 $1$（$3$ 分）：$n=1$。 子任务 $2$（$7$ 分）：$n=18$。 子任务 $3$（$10$ 分）：$n=100$，$s$ 中不同的正整数不超过 $18$ 个。 子任务 $4$（$20$ 分）：$n=100$，不存在 $1\leq i \neq j \leq n$，使得 $s_i=s_j$。且保证数据随机。 子任务 $5$（$20$ 分）：$1\leq s_1, s_2, \ldots, s_n \leq 100$。 子任务 $6$（$20$ 分）：$1\leq n \leq 10^4$。 子任务 $7$（$20$ 分）：无特殊限制。 ------ 谨以此题庆祝刀剑10周年。~~好像晚了几个月...~~ ### 题目来源 [MtOI2019 Extra Round](https://www.luogu.org/contest/22840) T4 出题人：CYJian 验题人：suwAKow