Description

你有 $n$ 个数字 $a_1,a_2,\dots,a_n$，需要进行恰好 $k$ 次操作。 每次操作可以任选一个数字 $a_i$，并将它乘以 2。

请你求出：$k$ 次操作后，所有数字之和的最小可能值。

由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。 注意：必须先计算最小和，再取模，而不是先取模再求最小值。

Format

Input

第一行输入两个整数 $n,k$。 $(1\le n\le 2\times 10^5,\ 0\le k\le 10^9)$

第二行输入 $n$ 个整数 $a_i$。 $(1\le a_i\le 10^9)$

Output

输出一行一个整数，表示 $k$ 次操作后最小总和对 $10^9+7$ 取模的结果。

Samples

3 3
7 2 1

15

Limitation

1s, 1024KiB for each test case.