Sum of Spanning Tree Weights

Given a weighted graph with (n) vertices and (m) edges, which can be either undirected or directed, compute the sum of the weights of all distinct spanning trees modulo (10^9+7). Here, the weight of a spanning tree (T) is defined as the product of the weights of all edges in (T).

Note:

1. For an undirected graph, a spanning tree is defined in the usual way.
   
2. For a directed graph, a spanning tree refers to an out‐branching with vertex (1) as the root (i.e. every vertex except (1) has exactly one incoming edge and there is a directed path from (1) to every other vertex).
   
3. Two spanning trees (T_1) and (T_2) are considered different if and only if there exists an edge (e) such that (e \in T_1) but (e \notin T_2).

inputFormat

The first line of input contains three integers (n), (m) and (d) where (n) is the number of vertices, (m) is the number of edges, and (d) is a flag (0 for an undirected graph and 1 for a directed graph).

Each of the next (m) lines contains three integers (u), (v) and (w) representing an edge from vertex (u) to vertex (v) with weight (w).

For undirected graphs (when (d = 0)), each edge is bidirectional. For directed graphs (when (d = 1)), consider only spanning trees that are out‑branchings rooted at vertex (1) (i.e., ignore any edge with (v = 1)).

outputFormat

Output a single integer, which is the sum of the weights of all distinct spanning trees modulo (10^9+7).

sample

4 4 0
1 2 1
2 3 2
3 4 3
4 1 4

50