[Cnoi2021] 矩阵

Rumia 喜欢矩阵快速幂，而 Cirno 觉得这是平凡的。 为了说服 Rumia，Cirno 提出了这样一个问题。

给定两个长度为 $n$ 的序列 $\{a_n\}$，$\{b_n\}$ 与一个整数 $k$。 设矩阵 $A$ 满足 $A_{ij}=a_i\times b_j$，求 $A^k$ 的所有元素的和在模 $998244353$ 意义下的结果。

第一行两个整数 $n$，$k$。 第二行 $n$ 个整数，用空格隔开，表示 $\{a_n\}$。 第三行 $n$ 个整数，用空格隔开，表示 $\{b_n\}$。

一行，一个整数，表示 $A^k$ 的所有元素的和在模 $998244353$ 意义下的结果。

3 0
1 2 3
4 5 6

3

3 3
1 2 3
4 5 6

92160

**数据范围** 对于 $100\%$ 的数据保证 $1 \le n \le 10^5$，$0\le k < 998244353$，$|a_i|,|b_i| \le 10^9$。 **子任务** Subtask1（10 points）：$n, k \le 50$。 Subtask2（20 points）：$n \le 100$。 Subtask3（20 points）：$n \le 1000$。 Subtask4（50 points）：无特殊限制。 **提示** 矩阵乘法的定义参考[百度百科](https://baike.baidu.com/item/%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/5446029?fr=aladdin)页面。 本题中 $A^0$ 表示[单位矩阵](https://baike.baidu.com/item/%E5%8D%95%E4%BD%8D%E7%9F%A9%E9%98%B5/8540268?fr=aladdin)。