Calculate the \(N \times N\) matrix \(R\) equal to

\[(\sum_{i=0}^{K} f_i^2 \cdot M^i) \mod 998244353,\]

where \(f_i\) is the \(i^{th}\) Fibonacci number, \(f_0 = f_1 = 1\), \(K\) is a positive integer, and \(M\) is a given matrix of integers.

Input

The first line contains positive integer \(N\), denoting the number of rows and columns in the matrix \(M\). The second line contains the integer \(K\).

Matrix \(M\) is described by the next \(N\) lines, each containing \(n\) integers separated by spaces.

• \(1 \le N \le 50\)
• \(1 \le K < 10^{18}\)
• \(0 \le M_{ij} \le 998244353\)

Output

Print matrix \(R\) in \(n\) lines, each containing \(n\) integers.

Example

Input 1:

1
5
1

Output 1:

104