已知一个整数序列 $a_0,a_1,\cdots$ 满足以下线性递推关系：

$$\forall i \geq n, a_i \equiv \sum_{k=1}^n c_ka_{i-k} \pmod {998\,244\,353}$$

给定 $a_0,a_1,\cdots,a_{n-1}$，$c_1,c_1,\cdots,c_{n}$ 与 $k$，你想要计算 $a_k$ 取模 $998\,244\,353$ 的值。

输入格式

输入的第一行包含两个整数 $n,k$。

接下来一行，包含 $n$ 个整数 $a_0, a_1, \cdots, a_{n-1}$。

接下来一行，包含 $n$ 个整数 $c_1, c_1, \cdots, c_{n}$。

输出格式

输出一行一个整数，表示答案。

样例数据

样例 1 输入

3 10
2 5 3
1 4 6

样例 1 输出

58953

样例 2 输入

5 75789123
4 6 1 3 8
2 5 0 0 9

样例 2 输出

71403842

样例 3 输入

6 1999999
2 3 4 5 6 7
0 0 0 0 0 0

样例 3 输出

0

子任务

对于所有数据，$1 \leq n \leq 10^5$，$0 \leq k \leq 10^9$，$0 \leq a_i,c_i < 998\,244\,353$。