Cirno’s Present

One day, three fairies, Sunny, Luna and Star visited Cirno’s house. Cirno was very happy, so she decided to give a present to them.
Cirno’s present was a tree with N nodes. Each node of the tree has an equal possibility to be owned by one of Sunny, Luna or Star. After having decided every node’s owner, Cirno cut the edges that connect different owner’s nodes, after which each of the three fairies got some connected component of nodes (possibly none).
Then each of the three fairies had to spend some magical energy repairing the components she got. Suppose she had X components containing odd number of nodes and Y components containing even number of nodes, the magical energy she would spend equals max(0, X - Y ).
Cirno would compensate for the energy they spent with some food, so she asked you the expectation of the total energy the three fairies would spend, and your task is to find out the answer.
To make it simpler, as it’s easy to prove the multiplication of the expectation and the Nth power of three makes an integer, your task is to find the remainder of the multiplication divided by 10⁹ + 7.

There are several test cases, please process till EOF.
Each test case starts with a line containing one integer N (1 <= N <= 300). Then follows N - 1 lines, each contains two integers u and v (1 <= u, v <= N), representing an edge between node u and node v.

For each test case, print the remainder of the product of the expected energy cost and the N-th power of three (actually, the remainder divided by 10⁹ + 7) in a line.

1
2
1 2
3
2 1
1 3

3
12
51

2013ACM/ICPC亚洲区南京站现场赛——题目重现