For a graph with n vertices and m edges, count the number of distinct minimum spanning trees in this graph. Two spanning trees are considered different if there exists an edge in one tree that does not exist in the other.
### Input
- The first line consists of two integers n,m.
- The next m lines, each containing three integers u,v,w representing an edge of weight w between u and v.
### Output
- Print the number of distinct minimum spanning trees modulo 31011.
### Constraints
- 1≤n≤100.
- 1≤m≤1000.
- 1≤u,v≤n.
- 1≤w≤109.
- The number of edges having the same weight does not exceed 10.
### Sample test
Input
46121131141232241341
Output:
8
