Bob is joining a cult!

Unfortunately, Bob does not know where the cult members are located at. The invitation only noted down the city (which is Ottawa, of course), and a hint that all five cult leader reside in different houses that have the same distance to each other.

The city can be represented as a tree with \(N\) houses (represented as nodes) and \(N - 1\) bi-directional roads (represented as edges), each with the same length. Can you help Bob count the number of combination of houses that satisfy this? Note that two combinations are different if at least one of the five nodes is not in the other combination.

For this problem, Python users should submit their submissions in PyPy over CPython.

Input

The first line of the standard input contains a single integer \(N\) \((1 \le N \le 5000)\), the number of houses in Ottawa. These houses are numbered from \(1\) to \(N\).

The next \(N - 1\) lines describe Ottawa's road network, with the \(i\)-th line containing two integers \(a\) and \(b\) \((1 \le a \lt b \le N)\), indicating that there is a direct road between the houses \(a\) and \(b\).

Output

Output a single integer, representing the number of possible locations of the cult members. Note that the answer may not fit in a standard 32-bit integer.

Subtasks

Note that you will be required to pass the sample input to receive points for the subtasks.

Subtask 1 [20%]

\(1 \le N \le 10\)

Subtask 2 [80%]

No additional constraints.

Sample Input 1

6
1 2
1 3
1 4
1 5
1 6

Sample Output 1

1

Explanation for Sample Output 1

The only valid combination of locations is done by selecting \(2, 3, 4, 5, 6\) as the cult locations. The distance between each pair of the selected cities has a distance of \(2\).