F - go up stairs (hard)

配点: 650点

問題文

この問題では E_2 と制約が異なっています。

$X$ 段の階段があり、今くしらくんは $0$ 段目にいます。
$N$ 種類の移動方法があり、$i$ 番目の移動を選択すると、いまくしらくんがいる階段の段数を $s$ として、 $min(X, s+A_i)$ へ移動します。くしらくんが $X$ 段目に到達したら移動を終えます。
くしらくんが階段を上る方法は何通りありますか。答えを $998244353$ で割ったあまりを出力してください。

制約

• $1≦N≦300$
• $1≦X≦10^{12}$
• $1≦A_i≦300$
• $A_i$ は全て異なる
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力してください。

入出力例1

• 入力

2 5
2 4

• 出力

5

階段の上り方は以下の$5$通りあります。

• $(2, 2, 2)$
• $(2, 2, 4)$
• $(2, 4)$
• $(4, 2)$
• $(4, 4)$

入出力例2

• 入力

3 105
20 30 50

• 出力

85

入出力例3

• 入力

10 10000000000
1 2 3 4 5 6 7 8 9 10

• 出力

285342160

998244353 で割ったあまりを出力することに気を付けてください。