Description

Yuan defines the weight of a set $S$ as $\dfrac{\sigma(S)}{\pi(S)}$, where $\sigma(S)=\sum\limits_{x \in S}x$ is the sum of all elements in $S$, and $\pi(S)=\prod\limits_{x \in S}x$ is the product of all elements in $S$. Tian asks him: what is the sum of the weights of all subsets of a set $S$? Yuan quickly computes the answer. Tian then asks: what is the sum of the sums of the weights of all subsets of all subsets? Yuan also computes it quickly. So Tian asks one more question: in the question there are a total of $k$ layers of all subsets. Now Yuan cannot finish it, so he asks you for help. Yuan does not need an excessively large number, so you only need to output the answer modulo $p$.

Input Format

The first line contains three positive integers $n,k,p$, where $n$ is the number of elements in $S$.

The second line contains $n$ positive integers, representing the elements of $S$.

Output Format

Output one positive integer as the answer. It is guaranteed that the answer is meaningful modulo $p$.

3 1 7
1 2 3

3

3 10 7
1 2 3

4

Hint

Brief statement of the problem:

Let $f_0(S)=\dfrac{\sigma(S)}{\pi(S)}$, and $f_k(S)=\sum\limits_{T \subseteq S}f_{k-1}(T)$. Here $\sigma(S)=\sum\limits_{x \in S}x$ is the sum of all elements in $S$, and $\pi(S)=\prod\limits_{x \in S}x$ is the product of all elements in $S$. Given $n,k,p$ and the set $S$, find $f_k(S) \bmod{p}$.

Sample explanation:

Due to space limits, only sample $1$ is explained.

Enumerate subsets:

$\emptyset$, with $f_0$ value $0$;

$\{1\}$, with $f_0$ value $1$;

$\{2\}$, with $f_0$ value $1$;

$\{3\}$, with $f_0$ value $1$;

$\{1,2\}$, with $f_0$ value $\dfrac{3}{2}$;

$\{1,3\}$, with $f_0$ value $\dfrac{4}{3}$;

$\{2,3\}$, with $f_0$ value $\dfrac{5}{6}$;

$\{1,2,3\}$, with $f_0$ value $1$;

The total sum is $\dfrac{23}{3}$, which is $3$ modulo $7$.

Constraints:

For $30\%$ of the testdata, $n \le 13,k=1$.

For $70\%$ of the testdata, $n \le 10^3$.

For $100\%$ of the testdata, $1 \le n \le 7 \times 10^6,1 \le k \le 10^{18},1 \le x_i<p,1<p<2^{31},p$ is prime, and all $x_i$ are distinct.

The input size of this problem is large. You may use the fast input template from the contest statement to speed up reading.

Translated by ChatGPT 5