该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

优优给出了长度为 $n$ 的序列 $a$ 和一个正整数 $k$。

优优可以进行 $k$ 次操作，每次操作，优优需要选择一个下标 $i \in [1,n]$，让 $a_i$ 变成 $2\times a_i$。

请你告诉优优，k 次操作以后 $a_1+a_2+…+a_n$ 的值最小可以是多少，由于答案可能很大，你需要输出答案对 $10^9+7$ 取模。

输入格式

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

第二行，给定 $n$ 个正整数 $a_1,a_2,…,a_n$。

输出格式

输出一行，包含输出一个整数，表示答案。

样例

3 3
7 2 1

15

10 10
2 3 4 5 6 7 8 9 10 11

118

10 1000000
2 3 4 5 6 7 8 9 10 11

855687435

11 1000000000
2 3 4 5 6 7 8 91313 10 111111 998244353

606293891

数据范围与提示

• 对于 $20\%$ 的数据，$1 \leq n,k \leq 10$​​。
• 对于 $60\%$ 的数据，$1 \leq n,k \leq 1000$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5,1 \leq k \leq 10^9,1 \leq a_i \leq 10^9$。