题目背景

在 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 T4

出题人：CYJian

验题人：suwAKow