Around the World

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$) — the number of vertexes and edges in the graph. The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$w_i$$$ ($$$1 \le a_i, b_i \le n, a_i \neq b_i, 0 \le w_i < 32$$$) — the endpoints of the $$$i$$$-th edge and its weight. It's guaranteed there aren't any multiple edges, the graph is connected and there isn't any simple cycle of length greater than $$$3$$$ which passes through the vertex $$$1$$$.

Output:

Output the answer modulo $$$10^9+7$$$.

Sample Input:

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

Sample Output:

2

Sample Input:

7 9
1 2 0
1 3 1
2 3 9
2 4 3
2 5 4
4 5 7
3 6 6
3 7 7
6 7 8

Sample Output:

1

Sample Input:

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

Sample Output:

6

Note:

The pictures below represent the graphs from examples. In the first example, there aren't any nontrivial cycles with cost $$$0$$$, so we can either remove or keep the only edge incident to the vertex $$$1$$$. In the second example, if we don't remove the edge $$$1-2$$$, then there is a cycle $$$1-2-4-5-2-1$$$ with cost $$$0$$$; also if we don't remove the edge $$$1-3$$$, then there is a cycle $$$1-3-2-4-5-2-3-1$$$ of cost $$$0$$$. The only valid subset consists of both edges. In the third example, all subsets are valid except for those two in which both edges $$$1-3$$$ and $$$1-4$$$ are kept.