Description

Little S has just learned about spanning trees. Being clever, he came up with a question:
Given a weighted undirected complete graph with $n$ vertices, find the sum of the $k$-th powers of the weights of all spanning trees.
The weight of a tree is defined as the sum of the weights of all its edges.

Since he cannot solve it, you have to do it.
Because the answer may be very large, output the result modulo $998244353$.

Input Format

The first line contains two non-negative integers $n, k$, as described above.
The next $n$ lines each contain $n$ integers, representing the adjacency matrix of this weighted undirected complete graph.
Let $w_{i,j}$ denote the entry in row $i$ and column $j$ of the matrix, and it is guaranteed that:
$w_{i,i} = 0$, and $w_{i,j} = w_{j,i}$.

Output Format

Output one line containing one integer, representing the answer modulo $998244353$.

3 1
0 0 1
0 0 1
1 1 0

4

Hint

Constraints:

For $20\%$ of the testdata: $1 \le n \le 5$.
For another $10\%$ of the testdata: $k = 0$.
For another $10\%$ of the testdata: $k = 1$.
For $60\%$ of the testdata: $1 \le n \le 15$.
For another $15\%$ of the testdata: $1 \le k \le 15$.
For $100\%$ of the testdata: $1 \le n \le 30$, $0 \le k \le 30$, $0 \le w_{i,j} \le 998244352$.

Note that $0^0 = 1$.

Translated by ChatGPT 5