P7489 「Stoi2031」手写的从前

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

远定义一个集合 $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$ 时有意义。

#### 简述版题意： 令 $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