선형 점화 수열의 K번째 항

정수 수열 $(a_i)$은 다음 선형 점화식을 만족한다:

$a_{i} \equiv \sum_{j=1}^{d} c_j a_{i - j} \pmod{998244353},\ i\geq d$

$a_0,a_1,\ldots,a_{d-1}$가 주어질 때, $a_k \bmod 998244353$을 출력한다.

제약 조건

• $1 \leq d \leq 100000$
• $0 \leq k \leq 1000000000000000000$
• $0 \leq a_i \lt 998244353\ (0 \leq i \leq d-1)$
• $0 \leq c_i \lt 998244353\ (1 \leq i \leq d)$

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

$a_k$