Subtree Centroids

Given a tree with \(n\) nodes where each node is labeled from \(1\) to \(n\) and the tree is defined as a connected acyclic graph (i.e. having \(n-1\) edges and a unique path between any two nodes), you are asked to count the number of connected subtrees that have exactly the same centroid(s) as the original tree.

The centroid of a tree is defined as follows: For each vertex \(i\), remove it from the tree. Assume the removal of \(i\) leaves \(k\) connected components with sizes \(s_1, s_2, \dots, s_k\). Let \(d(i)=\max\{s_1, s_2, \dots, s_k\}\). The centroid(s) of the tree are the vertex (or vertices) \(i\) for which \(d(i)\) is minimized. Note that a tree may have either one or two centroids.

A connected subtree is defined as a set of vertices (with its induced edges) that is connected. The task is to compute the number of such subtrees whose centroid set, computed in the same way within the subtree, is exactly the same as the centroid set of the original tree. Output the count modulo \(10007\).

Input Format: The first line contains a single integer \(n\) representing the number of nodes in the tree. Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\).

Output: A single integer, the number of connected subtrees that have the same centroid(s) as the given tree, taken modulo \(10007\).

inputFormat

The first line contains an integer \(n\) (the number of nodes). The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between vertices \(u\) and \(v\).

outputFormat

Output the number of connected subtrees with the same centroid(s) as the original tree modulo \(10007\).

sample

1

1