Tree Path Minimum Distance Sum

You are given a tree with n nodes. For any three nodes u, v, and i, define the function \[ f(u,v,i)=\min\{\text{dis}(x,i)\mid x \text{ lies on the unique path from } u \text{ to } v\} \] where a node x lies on the path between u and v if and only if \[ \text{dis}(u,x)+\text{dis}(v,x)=\text{dis}(u,v). \] Here, \(\text{dis}(u,v)\) denotes the number of edges on the unique path between nodes u and v, with \(\text{dis}(u,u)=0\).

Your task is to compute \[ S=\sum_{u=1}^{n}\sum_{v=u+1}^{n}\sum_{i=1}^{n} f(u,v,i)\pmod{10^9+7}. \]

Note: Since the input tree is unweighted and contains n nodes, you are guaranteed that the path between any two nodes is unique. The constraints are small so that a solution with \( O(n^4)\) time complexity passes.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 50), the number of nodes in the tree.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating there is an edge between nodes u and v (the tree is undirected).

outputFormat

Output a single integer, the value of S defined above, taken modulo \(10^9+7\).

sample

1

0