线性递推序列的第 k 项（Kth term of Linearly Recurrent Sequence）

问题描述

一个整数序列 $(a_i)$ 满足如下线性递推关系：

$$a_i \equiv \sum_{j=1}^{d} c_j a_{i-j} \pmod{998244353}, \quad \text{对所有 } i \ge d.$$

给定初始项 $a_0, a_1, \dots, a_{d-1}$ 和系数 $c_1, c_2, \dots, c_d$，求第 $k$ 项 $a_k \bmod 998244353$。

约束条件

• $1 \leq d \leq 10^5$
• $0 \leq k \leq 10^{18}$
• $0 \leq a_i < 998244353$ （$0 \le i \le d-1$）
• $0 \leq c_i < 998244353$ （$1 \le i \le d$）

输入

$d\ k$
$a_0\ a_1\ \cdots\ a_{d-1}$
$c_1\ c_2\ \cdots\ c_d$

输出

$a_k$

2 5
1 1
1 1

8