You are given $n$ numbers $a_1, a_2, \dots, a_n$. You need to perform $k$ operations. In each operation, you choose a number $a_i$ and multiply it by $2$. After $k$ operations, what is the minimum possible sum of all the numbers?

Since the answer can be very large, you only need to output the result modulo $10^9 + 7$.

Input

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \times 10^5$, $0 \le k \le 10^9$). The second line contains $n$ integers, where the $i$-th integer represents $a_i$ ($1 \le a_i \le 10^9$).

Output

Output a single integer representing the minimum sum of all numbers after $k$ operations, modulo $10^9 + 7$. Note that you should calculate the minimum sum first and then take the modulo $10^9 + 7$, rather than taking the modulo of the numbers before finding the minimum.

Examples

Input 1

3 3
7 2 1

Output 1

15