P12285 [蓝桥杯 2024 国 Python A] 药剂

小蓝今天的实验内容是合并 $N$ 瓶试剂。每瓶试剂初始都有一个魔法值 $a_i$，所有魔法值都是正整数。 每次小蓝会随机从手头的试剂中选出两瓶，将其合并。合并时，两瓶试剂会发生化学反应，产生强大的力量，也有可能效果没有那么好。但无论如何，小蓝会得到一瓶全新的，可以和其他试剂合并的试剂。我们认为，小蓝在合并两瓶试剂时，如果两瓶试剂的魔法值分别是 $x$ 和 $y$，有 $\frac{1}{2}$ 的概率，小蓝得到的新试剂魔法值为 $x+y$，对于另 $\frac{1}{2}$ 概率，小蓝得到的新试剂的魔法值为 $xy$。 像这样，小蓝重复合并操作 $n-1$ 次，最后只会剩下一瓶试剂。小蓝希望知道，最后这瓶试剂的魔法值期望是多少。为了方便，假定这个值是 $ans$，你只需要告诉小蓝，$ans$ 乘上 $2^{n-1}\displaystyle \prod_{i=2}^{n}C_i^2$ 的结果，其中 $C_i^2$ 是组合数。不难证明这个值一定是一个整数。但这个乘积显然太大了，小蓝只希望你告诉她这个乘积对整数 $mo$ 取模之后的结果。

输入的第一行包含两个正整数 $N, mo$，用一个空格分隔。 第二行包含 $N$ 个正整数，相邻整数之间使用一个空格分隔，其中第 $i$ 个正整数表示第 $i$ 瓶试剂的魔法值 $a_i$。

输出一行包含一个整数表示答案，即最后一瓶试剂魔法值的期望乘上 $2^{n-1}\displaystyle \prod_{i=2}^{n}C_i^2$ 的结果。

### 样例说明 可能的合并情形较多，这里给出样例中两种可能的情况： - 第一次小蓝随机选中魔法值为 $1$ 和 $3$ 的试剂进行合并，得到魔法值为 $1+3=4$ 的一瓶新的试剂。 - 然后小蓝对仅剩的两瓶试剂进行合并，得到 $4 \times 2=8$ 的一瓶试剂。 - 因此这种情况最终试剂的魔法值为 $8$。 又或者： - 第一次小蓝随机选中魔法值为 $1$ 和 $2$ 的试剂进行合并，得到魔法值为 $1 \times 2=2$ 的一瓶新的试剂。 - 然后小蓝对仅剩的两瓶试剂进行合并，得到 $2+3=5$ 的一瓶试剂。 - 因此这种情况最终试剂的魔法值为 $5$。 ### 评测用例规模与约定 - 对于 $30\%$ 的评测用例，$1 \leq N \leq 5$，$mo = 10^9 + 7$； - 对于 $50\%$ 的评测用例，$1 \leq N \leq 50$，$mo = 10^9 + 7$； - 对于 $70\%$ 的评测用例，$1 \leq N \leq 300$，$mo = 10^9 + 7$； - 对于 $80\%$ 的评测用例，$mo = 10^9 + 7$； - 对于所有评测用例，$1 \leq N \leq 3000$，$1 \leq a_i \leq 10^9$，$1 \leq mo \leq 10^9 + 7$。