题目描述

小S 刚刚学习了生成树的知识，聪明的他想出了一个问题：
给定一个 $n$ 个点的带权无向完全图，求其所有生成树权值的 $k$ 次方之和。
定义一个树的权值，为其所有边权值和。

因为他不会，所以你要来做这题。
由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

第一行两个非负整数 $n,k$，意义如题目描述。
接下来 $n$ 行，每行 $n$ 个整数，为这个带权无向完全图的邻接矩阵表示。
设 $w_{i,j}$ 表示矩阵的第 $i$ 行第 $j$ 列，保证：
$w_{i,i}=0$，且 $w_{i,j}=w_{j,i}$

输出格式

输出一行一个整数表示答案对 $998244353$ 取模的结果。

3 1
0 0 1
0 0 1
1 1 0

4

提示

数据范围：

对于 $20\%$的数据： $1\le n\le 5$
对于另外 $10\%$ 的数据： $k = 0$
对于另外 $10\%$ 的数据： $k = 1$
对于 $60\%$ 的数据： $1\le n \le 15$
对于另外 $15\%$ 的数据： $1\le k \le 15$
对于 $100\%$ 的数据：$1\le n \le 30$，$0 \le k \le 30$，$0\le w_{i,j} \le 998244352$

注意 $0^0 = 1$