今有一个数列 $A_0, A_1, A_2, \cdots$，它满足这样一个递推式

$$ A_j = \sum_{i=1}^k {B_iA_{j-i}} $$

现在给你 $n$、$k$、$B_1 \sim B_k$ 和 $A_0 \sim A_{k-1}$，请你输出 $A_n$ 对 $998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数）取模后的值。

输入格式

第一行两个正整数 $n, k$。

第二行 $k$ 个非负整数表示 $A_0 \sim A_{k-1}$。

第三行 $k$ 个非负整数表示 $B_1 \sim B_k$。

输出格式

一个整数表示答案。

样例一

input

7 2
1 1
1 1

output

21

限制与约定

对于 $100\%$ 的数据，保证 $1 \le n \le {10}^9,1 \le k \le 5\times {10}^4,0 \le A_0, A_1, \ldots , A_{k-1}, B_1, B_2, \ldots , B_k < 998244353$。

时间限制：$7\texttt{s}$

空间限制：$512\texttt{MB}$