【题目描述】

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入1】

6 2
1 1 4 5 1 4

【样例输出1】

3740

【样例输入2】

10 10

【数据范围与提示】

对于 $40\%$ 的数据，$n\le100$。

对于 $100\%$ 的数据，$n\leq 3000$，$0\le a_i,k\le10^9$。