You are given an array A of non-negative integers. You can pick any non-empty subset, S from the array A. The score of a subset S is the sum of the elements in S raised to the power of K, i.e. for a subset S={s₁,s₂,…,s_m}, the score of S is (s₁+s₂+…,s_m)^K. Output the sum of scores over all possible non-empty subsets of A modulo 10⁹ + 7.

Input

The first line consists of two integers N (1 ≤ N ≤ 1000) and K (1 ≤ K ≤ 300), Then N integers follow: a₁,a₂…,a_n (1 ≤ a_i ≤ 10⁹)

Examples

Input:

3 2
1 2 4

Output:

140

Note

There are 7 possible non empty subsets:

{1}, 1²=1

{2}, 2²=4

{4}, 4²=16

{1,2}, 3²=9

{1,4}, 5²=25

{2,4}, 6²=36

{1,2,4}, 7²=49

The total of all of them is 140.

Scoring

this is code-golf, so the shortest code in bytes wins