406591: GYM102448 J Jingle Bells

Christmas is coming, and Kinho was building his christmas tree! As a good programmer, his tree is, of course, an acyclic, undirected and connected graph, with $$$N$$$ vertices and $$$N-1$$$ unweighted edges.

Kinho also has 5 buckets of ink, with colors {1, 2, 3, 4, 5}, having an infinite amount of ink on each bucket. The absence of color is indicated with the number 0. Initially, all edges of the tree had no color, but then he decided to paint some edges with one of the five available colors.

Kinho quickly got tired and asked for Tfg's help. He would need to continue painting the tree, in a way that it became beautiful.

A tree is beautiful if all of its edges are painted, and there is no vertex with two or more adjacent edges with the same color.

Tfg likes beautiful trees, and then, in order to raise is excitement, he asked you how many ways are there to paint the entire tree. Two ways are considered different if they have at least one edge with a different color in each way.

Note that there will be edges which have been already painted by Kinho - and Tfg must not change them! He is only allowed to paint uncolored edges.

The first line of the input contains a single integer $$$N$$$, $$$1 \le N \le 10^{5}$$$, the number of vertices in the tree. Then, $$$N - 1$$$ lines follow, each of them containing three integers $$$u$$$, $$$v$$$ and $$$c$$$, $$$(1 \le u, v \le N)$$$, $$$(0 \le c \le 5)$$$, describing that there exists an edge between vertices $$$u$$$ and $$$v$$$ with color $$$c$$$. Remember that if $$$c = 0$$$, then the edge is uncolored.

You must output a single integer, the number of beautiful paintings, given the initial description of the tree. Since the number can be very large, output its remainder when divided by $$$10^{9} + 7$$$.

4
1 2 0
1 3 1
3 4 0

16

4
1 2 0
2 3 0
3 4 0

80