問題文

ある数列AAの先頭NN項が与えられます。
AAは下の規則に則っています。

  • Ai=Ai1+Ai2+...+AiN A_i = A_{i-1}+A_{i-2}+... +A_{i-N} (i>N) (i>N)

AKA_K998244353998244353 で割った余りを求めてください。

制約

  • 2N<K2×1052 ≤ N < K ≤ 2×10^5
  • 1Ai1091 ≤ A_i ≤ 10^9 (iN)(i≤N)
  • 入力は全て整数

入力

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

NN KK
A1A_1 A2A_2ANA_N

出力

AKA_K998244353998244353 で割った余りで出力してください。

サンプル

入力1
2 6
1 1
出力1
8

AA1,1,2,3,5,8,131,1,2,3,5,8,13…となるので66項目の88を出力します。

入力2
2 6
2 1
出力2
11

AA2,1,3,4,7,11,182,1,3,4,7,11,18…となるので66項目の1111を出力します。

入力3
4 1000
1 2 3 4
出力3
886028826

998244353998244353で割った余りを出力してください。

提出


Go (1.21)