問題文


~ の番号が付いたお菓子が入ったお菓子セットがある。お菓子にはそれぞれに体積が設定されている。お菓子 の体積は である。

食べたお菓子の体積の合計がちょうど になるようにお菓子をいくつか選んで食べる。

お菓子セットが 個あるときに食べたお菓子の体積の合計がちょうど になるように食べる方法の数を として、 で割ったあまりを出力するようなプログラムを作成せよ。


ただし、セットが違えばたとえ同じ種類のお菓子であっても区別される。

制約


入力


入力はすべて整数である。

N V K
v_1 v_2 ... v_N

出力


計算結果を一行に出力せよ。

サンプル


入力1
3 10 2
1 2 3
出力1
3

お菓子セット 個のときは食べたお菓子の体積の合計がちょうど になるように食べることはできないので、 です。

お菓子セット 個のときは、体積 のお菓子を 個、体積 のお菓子を 個、体積 のお菓子を 個食べる方法が 通り存在します。 さらに、体積 でないお菓子を全て食べる方法が 通りなので、 です。

より、答えは です。

入力2
2 2 2
1 1
出力2
7

となります。

お菓子セットの個数が 個のときに、お菓子セットを 個しか使わないことも許容されることに注意して下さい。

入力3
5 500 2022
1 1 149 334 2
出力3
613503506

Submit


Go (1.14)