Nested Subset Weight Sum

Given a set (S = {a_1,a_2,\dots,a_n}) of positive integers, define the weight of a nonempty subset (T \subseteq S) as [ w(T)=\frac{\sigma(T)}{\pi(T)}=\frac{\sum_{x\in T}x}{\prod_{x\in T}x}, ] where (\sigma(T)) is the sum of the elements in (T) and (\pi(T)) is their product. Let the first level answer be [ F(S)=\sum_{\emptyset\neq T\subseteq S} w(T). ] It turns out that an equivalent closed‐form expression is [ F(S)=\sum_{i=1}^n \prod_{\substack{1\le j\le n\j\ne i}}\Bigl(1+\frac{1}{a_j}\Bigr). ] We then define a sequence of functions by iterating the above operation. In particular, for a positive integer (k) we define the (k)-th level answer as the result of applying the "all subsets" operation (k) times on (S). A short computation shows that the final answer may be written in closed‐form as [ \mathrm{Ans} = \sum_{i=1}^n \frac{\prod_{\substack{1\le j\le n\j\ne i}}(k,a_j+1)}{\prod_{\substack{1\le j\le n\j\ne i}}a_j} \pmod{p}. ] Your task is to compute the answer modulo (p).\n\nInput Format:\ The first line contains a positive integer (n) (the size of (S)).\ The second line contains (n) positive integers (a_1,a_2,\dots,a_n).\ The third line contains a positive integer (k) (the number of times the subsets operation is applied).\ The fourth line contains a prime number (p) (the modulus).\ \nIt is guaranteed that (p) is prime and the final answer can be computed modulo (p).

inputFormat

The input consists of four lines:\n\nLine 1: An integer (n) ((1 \le n \le 15)).\nLine 2: (n) space‐separated positive integers (a_1,a_2,\dots,a_n) (each (\le 10^9)).\nLine 3: A positive integer (k) ((1 \le k \le 10^9)).\nLine 4: A prime number (p) (e.g. (10^9+7) or other, (p\le 10^9)).

outputFormat

Output a single integer, the final answer modulo (p).

sample

1
7
3
1000000007

1