問題文

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

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

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


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

制約

$1\leq N, V \leq 2000$

$1\leq K \leq 10^6$

$1\leq v_i \leq V$ $(1\leq i \leq N)$

入力

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

N V K
v_1 v_2 ... v_N

出力

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

サンプル

3 10 2
1 2 3

3

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

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

$f(1)+f(2)=0+3=3$ より、答えは $3$ です。

2 2 2
1 1

7

$f(1)=1, f(2)=6$ となります。

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

5 500 2022
1 1 149 334 2

613503506