You are given a tree consisting of n nodes. You are allowed to add an edge between any two nodes of the tree. Now, you are required to find the number of total distinct pentagons possible by adding an edge between any two nodes.
The side of the pentagon is defined as an edge between two nodes of the tree.
A tree is a connected graph without cycles.
Note: A polygon is unique if at least one side is different.
Since the answer can be very large, print it modulo 109+7.
Input format
- The first line of each test case contains an integer N denoting the number of nodes in the tree.
- Each of the next N−1 lines contains two nodes say U and V denoting an edge between them.
Output format
Print a single integer denotes the number of pentagons possible.
Constraints
1≤N≤3000001≤U,V≤N
Sample Input
6
1 2
2 3
3 4
4 5
5 6
Sample Output
2
First pentagon is by Adding an edge between 1 and 5 node, will create a pentagon having nodes 1,2,3,4,5 as its vertices.
Second pentagon is by Adding an edge between 2 and 6 node, will create a pentagon having nodes 2,3,4,5,6 as its vertices.
