Funny Tree (Extreme Version)

Orange is trying to find a permutation of nodes to represent a path around a tree. The tree has N nodes, and each edge has a weight.

Let d(u,v) be the maximum of the edge weights of the edges between nodes u and v.

Orange wants a long holiday to escape from his very annoying friends who try to read his whatsapp. Help him find the time it takes him to travel around the tree, formally the maximum value of Σ 2^d(p_i,p_i-1) across all permutations of vertices p₁,p₂,...,p_N. (Note that Σ refers to the summation symbol)

As this number could be large, output the result modulo 10⁹+7.

Input

First line contains 1 integer (2 ≤ N ≤ 100000)

Each of the next N-1 lines contains 3 integers u (1 ≤ u ≤ N), v (1 ≤ v ≤ N) and w (0 ≤ w ≤ N), representing an edge from node u to node v weight w.

Output

Output the length of the longest path!

Subtasks

Subtask 1 (18 points): 0 ≤ w ≤ 0
Subtask 2 (21 points): 0 ≤ w ≤ 1
Subtask 3 (26 points): 0 ≤ w ≤ min(N, 30)
Subtask 4 (35 points): 0 ≤ w ≤ N
Subtask 5 (0 points): Sample testcases

Sample 1

Input:
5
1 2 0
2 3 0
3 4 0
4 5 1
Output:
6
Explanation: {4,5,3,2,1}

Sample 2

Input:
10
2 1 1
3 1 1
1 4 0
5 1 2
6 4 1
2 7 2
8 4 2
8 9 3
6 10 0
Output:
42

Source

Well, orange really needed a stopper, and if this russian contest ex version can't stop someone then please let them claim their NOI first thanks :)