[北京省选集训2019]生成树计数

题目描述

小S 刚刚学习了生成树的知识,聪明的他想出了一个问题: 给定一个 $n$ 个点的带权无向完全图,求其所有生成树权值的 $k$ 次方之和。 定义一个树的权值,为其所有边权值和。 因为他不会,所以你要来做这题。 由于答案可能很大,请输出答案对 $998244353$ 取模的结果。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3 1
0 0 1
0 0 1
1 1 0

输出样例 #1

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$