DS '19 Day 2 P3 Inaho C

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 9.0s
Memory limit: 256M

Author:
Problem type

Inaho has stumbled across a sequence of integers a_0, a_1, a_2, \dots. He knows the values of the first N terms a_0 to a_{N-1}. He also knows that how to compute the rest of the sequence: it satisfies the following recursive formula: \displaystyle a_i = b_1 a_{i-1} + b_2 a_{i-2} + \dots + b_N a_{i-N} for all integers i \ge N and he already has the values of b. With this information, can you help him calculate a_K? Since this number may be large, please output it modulo 998\,244\,353.

Constraints

0 \le a_i, b_i \le 1\,000\,000\,000 for all i.
b_n \not\equiv 0 \pmod{998\,244\,353}
1 \le N \le 15\,000
0 \le K \le 10^{15}

In 20\% of the cases, 1 \le N \le 50.
In an additional 20\% of the cases, 1 \le N \le 2\,000.
In an additional 30\% of the cases, 1 \le N \le 8\,000.

Input Specification

The first line will contain two space-separated integers N and K.
The next line will contain N space-separated integers a_0, a_1, \dots, a_{N-1}.
The final line will contain N space-separated integers b_1, b_2, \dots, b_N.

Output Specification

Output a single integer, a_K \pmod{998\,244\,353}.

Sample Input

2 10
1 1
1 1

Sample Output

89

Comments

There are no comments at the moment.