题面：

你有一根木棍和一个神秘数字 $k$，木棍上有 $n-1$ 道划痕将木棍分成 $n$ 个部分，从左到右第 $i$ 个部分的长度为 $ai$。你可以沿着划痕把木棍切成任意多段，一段长度为 $x$ 的贡献是 $x$ 的 $n-1$ 次方，一种切割方案的权值是每段的权值和。

求所有 $2$ 的 $n-1$ 次方种切割方案的权值和。

输入格式：

第一行两个正整数 $n,k$。

第二行 $n$ 个正整数表示数组 $a$。

输出格式：

输出一行一个正整数表示答案对 $10^9+7$ 取模的结果。

样例：

输入：

6 2
1 1 4 5 1 4

输出：

3740

提示： 对于 $100$ 分的数据，$n<=3000,0<=ai,k<=10^9$

求解题思路