Description

Given two sequences of length $n$, $\{a_n\}$ and $\{b_n\}$, and an integer $k$.

Let matrix $A$ satisfy $A_{ij}=a_i\times b_j$. Find the sum of all elements in $A^k$ modulo $998244353$.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers separated by spaces, representing $\{a_n\}$.

The third line contains $n$ integers separated by spaces, representing $\{b_n\}$.

Output Format

One line containing one integer, representing the sum of all elements in $A^k$ modulo $998244353$.

3 0
1 2 3
4 5 6

3

3 3
1 2 3
4 5 6

92160

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$, $0 \le k < 998244353$, and $|a_i|, |b_i| \le 10^9$.

Subtasks

Subtask 1 (10 points): $n, k \le 50$.

Subtask 2 (20 points): $n \le 100$.

Subtask 3 (20 points): $n \le 1000$.

Subtask 4 (50 points): no special constraints.

Notes

For the definition of matrix multiplication, refer to the Baidu Baike page.

In this problem, $A^0$ denotes the identity matrix.

Translated by ChatGPT 5