题目背景

我看着你的脸 轻刷着和弦 情人节卡片 手写的永远 还记得广场公园 一起表演 学校旁糖果店 记忆里在微甜 ——《手写的从前》

题目描述

远定义一个集合 $S$ 的 权值 为 $\dfrac{\sigma(S)}{\pi(S)}$，其中 $\sigma(S)=\sum\limits_{x \in S}x$ 为 $S$ 中所有元素之和， $\pi(S)=\prod\limits_{x \in S}x$ 为 $S$ 中所有元素之积。甜问他，一个集合 $S$ 的 所有子集 的 权值 和是多少？远很快就算出了答案。甜又问，那 所有子集 的 所有子集 的 权值 和之和是多少？远又很快就算了出来。于是甜又问了一个问题，问题中总共有 $k$ 个 所有子集，这下远算不完了，所以他找你帮忙。远不需要回答一个太大的数，所以答案只要取模 $p$。

输入格式

第一行 $3$ 个正整数 $n,k,p$，其中 $n$ 为 $S$ 中元素的个数。

第二行 $n$ 个正整数，表示 $S$ 中的元素。

输出格式

输出一个正整数表示答案，保证答案在模 $p$ 时有意义。

3 1 7
1 2 3

3

3 10 7
1 2 3

4

提示

简述版题意：

令 $f_0(S)=\dfrac{\sigma(S)}{\pi(S)}$，$f_k(S)=\sum\limits_{T \subseteq S}f_{k-1}(T)$。其中 $\sigma(S)=\sum\limits_{x \in S}x$ 为 $S$ 中所有元素之和， $\pi(S)=\prod\limits_{x \in S}x$ 为 $S$ 中所有元素之积。给定 $n,k,p$ 和集合 $S$，求 $f_k(S) \bmod{p}$ 的值。

样例解释：

限于篇幅，只解释样例 $1$。

枚举子集：

$\emptyset$，$f_0$ 值为 $0$；

$\{1\}$，$f_0$ 值为 $1$；

$\{2\}$，$f_0$ 值为 $1$；

$\{3\}$，$f_0$ 值为 $1$；

$\{1,2\}$，$f_0$ 值为 $\dfrac{3}{2}$；

$\{1,3\}$，$f_0$ 值为 $\dfrac{4}{3}$；

$\{2,3\}$，$f_0$ 值为 $\dfrac{5}{6}$；

$\{1,2,3\}$，$f_0$ 值为 $1$；

总和为 $\dfrac{23}{3}$，模 $7$ 后为 $3$。

数据范围：

对于 $30\%$ 的数据，$n \le 13,k=1$。

对于 $70\%$ 的数据，$n \le 10^3$。

对于 $100\%$ 的数据，$1 \le n \le 7 \times 10^6,1 \le k \le 10^{18},1 \le x_i<p,1<p<2^{31},p$ 是质数，$x_i$ 互不相同。

本题读入量较大，可以选择使用比赛描述中的快速读入模板以加快读入速度。