Merging Reagents

You are given N reagent bottles. The i-th bottle starts with a positive integer magic value \(a_i\). In an experiment, you repeatedly merge two bottles until only one remains (i.e. perform \(N-1\) merge operations). When merging two bottles with magic values \(x\) and \(y\), a chemical reaction occurs and with probability \(\frac{1}{2}\) the resulting bottle has magic value \(x+y\) and with probability \(\frac{1}{2}\) it has magic value \(xy\).

Let \(ans\) be the expected magic value of the final reagent. You are not required to output \(ans\) directly. Instead, you must compute and output

[ \frac{\prod_{i=1}^{N} (2a_i+1)-1}{2} \times \Bigl(2^{N-1}\prod_{i=2}^{N}\binom{i}{2}\Bigr) \mod mo, ]

It can be shown that this value is an integer. Note that \(\binom{i}{2}\) denotes the binomial coefficient, i.e. the number of ways to choose 2 items from \(i\) items.

Hint: You may show that

[ E[2\cdot R + 1] = \prod_{i=1}^{N} (2a_i+1), ]

where \(R\) is the final reagent’s magic value. Consequently, a short calculation shows that

[ ans = \frac{\prod_{i=1}^{N} (2a_i+1)-1}{2}. ]

Furthermore, notice that

[ 2^{N-1}\prod_{i=2}^{N}\binom{i}{2} = N!\times (N-1)!. ]

Your task is to compute

[ \left(\frac{\prod_{i=1}^{N} (2a_i+1)-1}{2}\right) \times \left(N! \times (N-1)! \right) \mod mo. ]

</p>

inputFormat

The first line contains two integers \(N\) and \(mo\) (where \(mo\) is the modulus).

The second line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\), separated by spaces.

outputFormat

Output a single integer, the required result modulo \(mo\).

sample

2 1000000007
1 1

8