一种生成树的计算定理。

定义生成树的权值为所有该生成树中所有边权的乘积，则有如下结论：

邻接矩阵 $D$ 中 $d_{i,i}=$ 所有与节点 $i$ 相连的边的权值和，$d_{i,j}=0(i\neq j)$。

邻接矩阵 $L$ 中 $d_{i,j}=edge[i][j].w$ (注意无向图中 $d_{i,j}=d_{j,i}$)。

记基尔霍夫矩阵 $K=D-L$，$K'$ 为 $K$ 去掉第 $i$ 行与第 $i$ 列得到的余子式($i$ 可以任取)。

则有 $det(K')=$ 所有生成树的权值和。特别地，当所有边权为 $1$ 时所有生成树的权值和等于生成树个数。

邻接矩阵 $L$ 定义不变(但要注意边的有向性)。

如果邻接矩阵 $D$ 中 $d_{i,i}=$ 节点 $i$ 的所有入边的权值和。

记 $K'$ 为$K$ 去掉第 $i$ 行与第 $i$ 列得到的余子式，则 $det(K')=$ 所有以节点 $i$ 为根的外向树(边从根指向叶子节点)的权值和。

如果邻接矩阵 $D$ 中 $d_{i,i}=$ 节点 $i$ 的所有出边的权值和。

记 $K'$ 为$K$ 去掉第 $i$ 行与第 $i$ 列得到的余子式，则 $det(K')=$ 所有以节点 $i$ 为根的内向树(边从叶子节点指向根)的权值和。

洛谷p6178

给定一个 $n$ 个节点 $m$ 条带权边的图，输入 $t$ 表示图的有向性。

求其所有不同生成树的权值之和(如果是有向图，则求以 $1$ 为根的外向树)，对 $10^9+7$ 取模。