题目描述

有一个 $n$ $(1 \leq n \leq 50)$ 个点的带权无向图，其中 $(u, v)$ 的权值为 $w_{u,v}$ $(0 \leq w_{i,j} \leq 10^9, w_{i,j} = w_{j,i}, w_{i,i} = 0)$ 。我们定义生成树的权值为边权之和的 $k$ $(0 \leq k \leq 50)$ 次方。问所有生成树的权值之和，对 $10^9+7$ 取模。

输入格式

第一行，两个整数 $n, k$。

接下来 $n$ 行，每行 $n$ 个整数，表示 $w$。

输出格式

输出一个数，表示答案。

样例

3 1
0 1 2
1 0 3
2 3 0

12