已知一个整数序列 $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$。
| 子任务编号 | $n \leq $ | 分值 |
|---|---|---|
| $1$ | $100$ | $5$ |
| $2$ | $1\,000$ | $20$ |
| $3$ | $5\,000$ | $15$ |
| $4$ | $20\,000$ | $5$ |
| $5$ | $30\,000$ | $15$ |
| $6$ | $40\,000$ | $5$ |
| $7$ | $60\,000$ | $10$ |
| $8$ | $80\,000$ | $10$ |
| $9$ | $10^5$ | $15$ |