P6178 【模板】Matrix-Tree 定理

给定一张 $n$ 个结点 $m$ 条边的带权图（可能为无向图，可能为有向图）。 定义其一个生成树 $T$ 的权值为 $T$ 中所有边权的乘积。 求其所有不同生成树的权值之和，对 $10^9+7$ 取模。 --- 注意： 1. 本题中，有向图的生成树指的是 **以 $1$ 为根的外向树**； 2. 两棵生成树 $T_1,T_2$ 不同，当且仅当存在存在一条边 $e$，满足 $e\in T_1,\ \ e\notin T_2$。

无

无

【样例 $1$ 解释】 样例 $1$ 中的无向图如左图所示：  右图为其一个权值为 $3\times 1\times 2\times 3=18$ 的生成树的例子。 --- 【样例 $2$ 解释】 样例 $2$ 中的有向图如左图所示：  右图为其一个权值为 $1\times 1\times 1\times 2=2$ 的生成树（以 $1$ 为根的外向树）的例子。 --- 【数据范围】 对于 $100\%$ 的数据：$1\leq n\leq 300,\ \ 1\leq m\leq 10^5,\ \ t\in \{0,1\},\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^9$。 对于测试点 $1,2,3,4,5,6$，$t=0$；对于测试点 $7,8,9,10,11$，$t=1$。 图中 **可能** 存在重边和自环，重边算作多条边。