已知一个整数序列 a0,a1,⋯ 满足以下线性递推关系:
\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 |