~ の番号が付いたお菓子が入ったお菓子セットがある。お菓子にはそれぞれに体積が設定されている。お菓子 の体積は である。
食べたお菓子の体積の合計がちょうど になるようにお菓子をいくつか選んで食べる。
お菓子セットが 個あるときに食べたお菓子の体積の合計がちょうど になるように食べる方法の数を として、 を で割ったあまりを出力するようなプログラムを作成せよ。
ただし、セットが違えばたとえ同じ種類のお菓子であっても区別される。
入力はすべて整数である。
N V K v_1 v_2 ... v_N
計算結果を一行に出力せよ。
3 10 2 1 2 3
3
お菓子セット 個のときは食べたお菓子の体積の合計がちょうど になるように食べることはできないので、 です。
お菓子セット 個のときは、体積 のお菓子を 個、体積 のお菓子を 個、体積 のお菓子を 個食べる方法が 通り存在します。 さらに、体積 でないお菓子を全て食べる方法が 通りなので、 です。
より、答えは です。
2 2 2 1 1
7
となります。
お菓子セットの個数が 個のときに、お菓子セットを 個しか使わないことも許容されることに注意して下さい。
5 500 2022 1 1 149 334 2
613503506