問題一覧 > 通常問題

No.444 旨味の相乗効果

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : はむこ / テスター : yosupot
2 ProblemId : 1291 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-11-09 17:45:11

問題文

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

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

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

入力

n c
a1 a2 ... an

1≤n≤80, n∈N
1≤c≤1018, c∈N
0≤ai≤109, ai∈Z

出力

問題文で定義される「c個の旨味の相乗効果」を、109+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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。