F - go up stairs (hard)

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点: 650点

問題文

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

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

制約

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

入力

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

NN XX
A1A_1 A2A_2 ... ANA_N

出力

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


入出力例1

  • 入力
2 5
2 4
  • 出力
5

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

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

入出力例2

  • 入力
3 105
20 30 50
  • 出力
85

入出力例3

  • 入力
10 10000000000
1 2 3 4 5 6 7 8 9 10
  • 出力
285342160

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

提出


Go (1.21)