Rank-One Matrix Power Sum

Given two sequences \(\{a_i\}_{i=1}^n\) and \(\{b_i\}_{i=1}^n\) of length \(n\) and an integer \(k\), consider the \(n \times n\) matrix \(A\) defined by \(A_{ij} = a_i \times b_j\). Your task is to compute the sum of all elements of \(A^k\) modulo \(998244353\).

Hint: Since \(A = u v^T\) where \(u = [a_1, a_2, \dots, a_n]^T\) and \(v = [b_1, b_2, \dots, b_n]^T\), observe that for \(k \ge 1\), we have

[ A^k = u,(v^T u)^{k-1},v^T ]

This implies that the sum of all elements in \(A^k\) is given by

[ \text{Answer} = \left(\sum_{i=1}^n a_i\right) \left(\sum_{i=1}^n b_i\right) \left(\sum_{i=1}^n a_i b_i\right)^{k-1} \mod 998244353. ]

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le 10^5,\ 1 \le k \le 10^9)\).

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) where \(0 \le a_i < 998244353\).

The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\) where \(0 \le b_i < 998244353\).

outputFormat

Output a single integer: the sum of all the elements of \(A^k\) modulo \(998244353\).

sample

3 2
1 2 3
4 5 6

450