P7489 "Stoi2031" Handwritten Past

> I look at your face, lightly strumming chords. A Valentine's Day card, handwritten forever. I still remember the plaza and the park, performing together. The candy shop next to the school, in my memory slightly sweet. — "Handwritten Past"

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$.

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 one positive integer as the answer. It is guaranteed that the answer is meaningful modulo $p$.

#### 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