P6178 [Template] Matrix-Tree Theorem

Given a weighted graph with $n$ vertices and $m$ edges (it may be undirected or directed). Define the weight of a spanning tree $T$ as the product of the weights of all edges in $T$. Find the sum of the weights of all distinct spanning trees, modulo $10^9+7$. --- Notes: 1. In this problem, a spanning tree of a directed graph means an **out-arborescence rooted at $1$**. 2. Two spanning trees $T_1, T_2$ are different if and only if there exists an edge $e$ such that $e\in T_1$ and $e\notin T_2$.

The first line contains three integers $n, m, t$, representing the number of vertices, the number of edges, and the type of the graph ($t=0$ for an undirected graph, $t=1$ for a directed graph). The next $m$ lines each contain three integers $u, v, w$. If $t=0$, it means there is an undirected edge between $u$ and $v$ with weight $w$. If $t=1$, it means there is a directed edge from $u$ to $v$ with weight $w$.

The first line contains one integer $ans$, which is the sum of spanning tree weights of the given graph modulo $10^9+7$.

[Sample $1$ Explanation] The undirected graph in sample $1$ is shown in the left figure:  The right figure shows an example spanning tree with weight $3\times 1\times 2\times 3=18$. --- [Sample $2$ Explanation] The directed graph in sample $2$ is shown in the left figure:  The right figure shows an example spanning tree (an out-arborescence rooted at $1$) with weight $1\times 1\times 1\times 2=2$. --- [Constraints] For $100\%$ of the testdata: $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$. For test points $1,2,3,4,5,6$, $t=0$; for test points $7,8,9,10,11$, $t=1$. The graph **may** contain multiple edges and self-loops. Multiple edges are counted as different edges. Translated by ChatGPT 5