問題文

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

• $X_i = A_i$ $(1 ≤ i ≤ N)$
• $X_i = \sum_{j=i-N}^{i-1} B_{j-i+N+1}X_j$ $(N < i)$

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

制約

• $1 ≤ N ≤ 100$
• $N < K ≤ 10^{18}$
• $1 ≤ A_i,B_i ≤ 10^{9}$ $(1 ≤ i ≤ N)$

入力

出力

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

サンプル

2 6
1 1
1 1

8

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

3 5
1 2 3
1 2 4

76

3 100
1 6 9
1 3 7

944459922

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