TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

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$.

Input Format

$d$ $k$
$a_ 0$ $a_ 1$ $\ldots$ $a_ {d-1}$
$c_ 1$ $c_ 2$ $\ldots$ $c_ d$

Output Format

$a_ k$

Sample Input 1

2 5
1 1
1 1

Sample Output 1

8

Hints

  • $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)$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 2097152 2097152
1 10000 2097152 2097152
2 10000 2097152 2097152
3 10000 2097152 2097152
4 10000 2097152 2097152
5 10000 2097152 2097152
6 10000 2097152 2097152
7 10000 2097152 2097152
8 10000 2097152 2097152
9 10000 2097152 2097152
10 10000 2097152 2097152
11 10000 2097152 2097152
12 10000 2097152 2097152
13 10000 2097152 2097152
14 10000 2097152 2097152
15 10000 2097152 2097152
16 10000 2097152 2097152
17 10000 2097152 2097152
18 10000 2097152 2097152
19 10000 2097152 2097152