You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 个点和 $n-1$ 条边组成的连通图称为树。删除树中的任意一条边，原图将不再连通，树上任意两点之间由唯一的一条简单路径相连。

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

• 这里以及下文中的「子树」若无特殊说明都是指无根树的子树，即包括「向上」的那棵子树，并且不包括整棵树自身。

显然，树的重心只有一个或者两个共两种可能，树的重心如果不唯一，则至多有两个，且这两个重心相邻。

现在，小 Z 有一棵 $n$ 个点的无根树，结点编号为 $1,2,\cdots,n$。小 Z 想知道，这棵树中有多少个不同的子树，使得子树和这棵树有相同的重心。

• 这里的相同，要求子树的重心个数和重心编号都和原本的树相同。

由于数量可能很大，只需要输出答案 $\bmod 10007$ 的结果。

输入格式

从 tree.in 文件读入数据。

第一行一个整数 $n$，树的结点数量。

接下来有 $n-1$ 行，每行输入两整数数 $x,y$（$1 \le x,y \le n$），表示编号为 $x$ 的点和编号为 $y$ 的点之间存在一条边，所有点的编号从 $1 \sim n$。

输出格式

输出到 tree.out 文件。

输出满足条件的子树的个数，由于这个数字较大，你只需要输出这个数字 $\bmod\ 10007$ 后的结果。

样例

2
1 2

1

3
1 2
2 3

2

5
1 2
1 3
2 4
2 5

6

样例4

此样例满足 $n\le 500$ 数据范围限制。

点击链接 ex_tree4.in 和 ex_tree4.out 下载大样例 4 的输入数据和输出数据。

样例5

此样例满足 $n\le 5000$ 数据范围限制。

点击链接 ex_tree5.in 和 ex_tree5.out 下载大样例 5 的输入数据和输出数据。

说明/提示

对于 $50 \%$ 的数据，满足 $1 \le n \le 500$。

对于 $100 \%$ 的数据，满足 $1 \le n \le 5000$。