题目描述

小蓝今天的实验内容是合并 $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$ 的结果。

3 1000000007
1 2 3

75

提示

样例说明

可能的合并情形较多，这里给出样例中两种可能的情况：

• 第一次小蓝随机选中魔法值为 $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$。