G. Just Visiting Relatives
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ruien is traveling to Asia from Canada. During the 14-hour long flight, he gets so bored he tries to steal his friend Alex's passwords.

All of Alex's passwords are encoded in a square matrix. However, to avoid remembering an entire matrix of numbers, Alex decides to remember only two sequences, so that he can compute the matrix by finding the product of these sequences. To puzzle any potential hacker even more, Alex never uses his square matrix directly, but instead uses the $$$K$$$th power of it.

Help Ruien compute this $$$K$$$th power. Specifically, for two sequences $$$a_1,...,a_N$$$ and $$$b_1,...,b_N$$$, let the $$$N$$$ by $$$N$$$ square matrix $$$A$$$ satisfy $$$A_{(i,j)}=a_i*b_j$$$. Let $$$B$$$=$$$A^K$$$.

Find the sum of the elements of $$$B$$$.

Output your answer modulo $$$998244353$$$.

Input

Line 1: Two integers, $$$N$$$ and $$$K$$$ ($$$1 ≤ N ≤ 10^5$$$, $$$0 ≤ K \lt 998244353$$$).

Line 2: Sequence $$$A$$$, the $$$i$$$th number being $$$a_i$$$ ($$$|a_i|≤ 10^9$$$).

Line 3: Sequence $$$B$$$, the $$$i$$$th number being $$$b_i$$$ ($$$|a_i|≤ 10^9$$$).

Output

Line 1: One integer, representing the sum of the elements of $$$B$$$, modulo $$$998244353$$$.

Example
Input
3 3
1 2 3
4 5 6
Output
92160
Note

$$$A$$$ is the matrix:

4 5 6

8 10 12

12 15 18