問題文

旨味の相乗効果と呼ばれる現象があります。
異なる旨味を掛けあわせることで、旨味の強さが格段に高まるというものです。
ここに旨味が$n$種類あります。それらの旨味の強さは$a_i$です。

$n$種類の旨味が織りなす「$c$個の旨味の相乗効果」は、以下のように決まります。
$n$種類の旨味から、重複を認めて$c$個を選びます。
選んだ$c$個が全て同じ種類の旨味成分であれば、相乗効果が生まれないので考えません。
そうでなければ、選んだ$c$個の旨味の強さを掛けあわせます。
$c$個の選び方としてありえる全ての組み合わせについて、この掛けあわせた値を足し合わせたものが「$c$個の旨味の相乗効果」です。

$n$種類の旨味の強さ${a_i}$と、正の整数$c$が与えられるので、「$c$個の旨味の相乗効果」を求めて下さい。
答えは非常に大きくなりうるので、$10^9+7$で割った余りを出力してください。

入力

$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}$

出力

問題文で定義される「$c$個の旨味の相乗効果」を、$10^9+7$で割った余りを1行で出力してください。 最後に改行してください。

サンプル

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