Problem Statement

There is a phenomenon called the synergy of umami.
It is the effect whereby combining different umami flavors dramatically increases the strength of the umami.
Here there are $n$ kinds of umami. Their strengths are $a_i$.

The "synergy of $c$ umami" produced by the $n$ kinds of umami is determined as follows.
From the $n$ kinds of umami, choose $c$ of them, with repetition allowed.
If the chosen $c$ are all the same kind of umami component, no synergy arises, so such a choice is not considered.
Otherwise, multiply together the strengths of the chosen $c$ umami.
The sum of these products over all possible combinations of choosing $c$ is the "synergy of $c$ umami".

Given the strengths ${a_i}$ of the $n$ kinds of umami and a positive integer $c$, find the "synergy of $c$ umami".
Since the answer can be very large, output the remainder when divided by $10^9+7$.

Input

$n\ c$
$a_1\ a_2\ ...\ a_n$

$1 \leq n \leq 80$, $n \in \mathbb{N}$
$1 \leq c \leq 10^{18}$, $c \in \mathbb{N}$
$0 \leq a_i \leq 10^9$, $a_i \in \mathbb{Z}$

Output

Output on one line the remainder when the "synergy of $c$ umami" defined in the problem statement is divided by $10^9+7$. Print a newline at the end.

Sample

3 2
2 3 4

26

3 3
2 3 4

186

3 3
2 3 3

132

2 10
1000000000 0

0

80 1000000000000000000
52 49 26 4 10 21 63 40 64 3 55 13 91 71 32 2 96 40 24 88 73 15 19 73 82 89 75 46 61 1 8 3 1 8 7 49 55 62 23 30 81 94 82 89 47 73 44 98 90 23 66 17 91 55 60 16 37 58 82 10 8 83 16 99 94 3 77 94 98 1 1 52 21 65 7 52 48 26 41 28

241856039