题目背景

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）：无特殊限制。

提示

矩阵乘法的定义参考百度百科页面。

本题中 $A^0$ 表示单位矩阵。