nnacci sequence (hard)

2 secs 1024 MB
akinyan

問題文


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

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

制約


入力



...
...

出力


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

サンプル


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

となるので、答えはです。

入力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.14)