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