nnacci sequence (hard)

2 secs 1024 MB
akinyan's icon akinyan

問題文

数列XXを次のように定めます。

  • Xi=AiX_i = A_i (1iN)(1 ≤ i ≤ N)
  • Xi=j=iNi1Bji+N+1XjX_i = \sum_{j=i-N}^{i-1} B_{j-i+N+1}X_j (N<i)(N < i)

長さ NN の数列 A,BA,B が与えられるので XKX_K を998244353で割った余りを求めてください。

制約

  • 1N1001 ≤ N ≤ 100
  • N<K1018N < K ≤ 10^{18}
  • 1Ai,Bi1091 ≤ A_i,B_i ≤ 10^{9} (1iN)(1 ≤ i ≤ N)

入力

NN KK
A1A_1 A2A_2 ... ANA_N
B1B_1 B2B_2 ... BNB_N

出力

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

サンプル

入力1
2 6
1 1
1 1
出力1
8

AA1,1,2,3,5,8...1,1,2,3,5,8...となるので、答えは88です。

入力2
3 5
1 2 3
1 2 4
出力2
76
入力3
3 100
1 6 9
1 3 7
出力3
944459922

998244353で割ることを忘れないでください。

提出


Go (1.21)