8974: [yosupo] Other - Kth term of Linearly Recurrent Sequence
[Creator : ]
Description
An integer sequence $(a_i)$ satisfies the following linear recurrence:
$a_{i} \equiv \sum_{j=1}^{d} c_j a_{i - j} \pmod{998244353},\ i\geq d$
Given $a_0,a_1,\ldots,a_{d-1}$, print $a_k \bmod{998244353}$.
$a_{i} \equiv \sum_{j=1}^{d} c_j a_{i - j} \pmod{998244353},\ i\geq d$
Given $a_0,a_1,\ldots,a_{d-1}$, print $a_k \bmod{998244353}$.
Input
$d$ $k$
$a_0$ $a_1$ $\ldots$ $a_{d-1}$
$c_1$ $c_2$ $\ldots$ $c_d$
$a_0$ $a_1$ $\ldots$ $a_{d-1}$
$c_1$ $c_2$ $\ldots$ $c_d$
Output
$a_k$
Constraints
$1 \leq d \leq 10^5$
$0 \leq k \leq 10^{18}$
$0 \leq a_i \lt 998244353\ (0 \leq i \leq d-1)$
$0 \leq c_i \lt 998244353\ (1 \leq i \leq d)$
$0 \leq k \leq 10^{18}$
$0 \leq a_i \lt 998244353\ (0 \leq i \leq d-1)$
$0 \leq c_i \lt 998244353\ (1 \leq i \leq d)$
Sample 1 Input
2 5
1 1
1 1
Sample 1 Output
8