生成树

题目描述 有一个带权的无向图，其中(𝑢𝑢, 𝑣𝑣)的权值为𝑤𝑤𝑢𝑢,𝑣𝑣 。

我们定义生成树的权值为边权之和的𝑘𝑘次方。

问所有生成树的权值之和，对109 + 7取模。

输入格式 第一行，两个整数𝑛𝑛, 𝑘𝑘。

接下来𝑛𝑛行，每行𝑛𝑛个整数，表示𝑤𝑤。

输出格式 输出一个数，表示答案。

样例输入 1 3 1 0 1 2 1 0 3 2 3 0

样例输出 1 12

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1满足𝑛𝑛 ≤ 5。

测试点2满足𝑛𝑛 ≤ 9。

测试点3,4满足𝑘𝑘 = 1。

测试点5,6满足0 ≤ 𝑤𝑤𝑖𝑖,𝑗𝑗 ≤ 3。

测试点7,8满足𝑘𝑘 ≤ 3。

对于所有数据，满足1 ≤ 𝑛𝑛 ≤ 50,0 ≤ 𝑘𝑘 ≤ 50,0 ≤ 𝑤𝑤𝑖𝑖,𝑗𝑗 ≤ 109 , 𝑤𝑤𝑖𝑖,𝑗𝑗 = 𝑤𝑤𝑗𝑗,𝑖𝑖 , 𝑤𝑤𝑖𝑖,𝑖𝑖 = 0。