Description

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$.

Input Format

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$.

Output Format

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

5 8 0
2 3 1
1 2 3
4 5 1
4 2 2
3 5 2
3 4 3
3 4 1
3 3 5

144

5 9 1
1 2 3
3 2 1
1 3 1
2 4 2
3 5 1
4 3 4
3 5 1
5 4 1
4 4 6

72

Hint

[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