[MtOI2019] 恶魔之树

题目背景

在 Kirito 和 Eugeo 还没有与 Alice 前往北之洞窟的时候,Eugeo 每天只能用龙骨斧砍恶魔之树——基家斯西达…… ![](https://cdn.luogu.com.cn/upload/image_hosting/95swctde.png) ~~请忽略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$ 取模的结果。

输入输出样例

输入样例 #1

3 998244353
1 2 3

输出样例 #1

24

输入样例 #2

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

输出样例 #2

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