P8110 [Cnoi2021] Matrix

Rumia likes matrix fast exponentiation, and Cirno thinks it is ordinary. To convince Rumia, Cirno proposed the following problem.

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

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

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

**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](https://baike.baidu.com/item/%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/5446029?fr=aladdin) page. In this problem, $A^0$ denotes the [identity matrix](https://baike.baidu.com/item/%E5%8D%95%E4%BD%8D%E7%9F%A9%E9%98%B5/8540268?fr=aladdin). Translated by ChatGPT 5