No.444 旨味の相乗効果

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : はむこはむこ / テスター : yosupotyosupot

0 ProblemId : 1291 / 出題時の順位表

問題文

旨味の相乗効果と呼ばれる現象があります。
異なる旨味を掛けあわせることで、旨味の強さが格段に高まるというものです。
ここに旨味が$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行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 2
2 3 4
出力
26

「$2$個の旨味の相乗効果」は2*3+3*4+4*2です。

サンプル2
入力
3 3
2 3 4
出力
186

「$3$個の旨味の相乗効果」は、2*2*3+2*2*4+2*3*3+2*3*4+2*4*4+3*3*4+3*4*4です。

サンプル2
入力
3 3
2 3 3
出力
132

「$3$個の旨味の相乗効果」は、2*2*3+2*2*3+2*3*3+2*3*3+2*3*3+3*3*3+3*3*3です。
旨味の強さが同じでも、旨味自体が違えば、重複して数えたことにはなりません。

サンプル3
入力
2 10
1000000000 0
出力
0

一方の旨味が0なので、相乗効果も0になってしまいました。

サンプル4
入力
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

提出ページヘ