帕秋莉的试剂

题目描述

帕秋莉有 $n$ 瓶魔法试剂，每瓶魔法试剂有一个价值 $a_i$。
帕秋莉每次会随机（等概率）选择两瓶试剂进行混合，来形成一瓶新的试剂（原先的试剂会消失）。
新的魔法试剂的新价值 $\frac{1}{2}$ 概率是 $x + y$，有 $\frac{1}{2}$ 概率是 $xy$（其中 $x, y$ 是原先两瓶试剂的价值）。
帕秋莉会不断混合魔法试剂直到她只剩一瓶试剂，她想要知道，最后的这瓶魔法试剂的期望价值是多少。
加入答案是 $x$，你只需要输出 $2^{n-1}x \prod^n_{i=2} C^2_i \mod m$，保证 $m$ 是一个奇质数。
可以发现输出是一个正整数。

输入格式

第一行两个正整数 $n, m$。
接下来一行 $n$ 个正整数描述 $a_i$ 表示各个魔法试剂的价值。

输出格式

一个正整数，表示答案。

样例

样例输入

3 1000000007
1 2 3

样例输出

75

数据规模与约定

对于 $30\%$ 的数据满足 $1 \le n \le 10$。
对于前 $50\%$ 的数据满足 $1 \le n \le 50$。
对于前 $70\%$ 的数据满足 $1 \le n \le 300$。
对于前 $80\%$ 的数据满足 $m=1000000007$。
对于前 $100\%$ 的数据满足 $1 \le n \le 3000, a_i \le 10^9$