分数: 1800 点
问题陈述
有一棵树 T 与 N 顶点,已编号 1 通过 N。 对于每个 1 ≤ i ≤ N - 1, i第一条边连接顶点 a_i 和 b_i.
Snuke 正在构建有向图 T' 通过任意指定每个边缘的方向 T。 2^{N - 1} 不同的构建方式 T'.)
对于固定 T',我们将定义 d(s,\ t) 对于每个 1 ≤ s,\ t ≤ N,如下:
- d(s,\ t) = (从顶点移动时必须逆着指定方向遍历的边数 s 到顶点 t)
特别是, d(s,\ s) = 0 对于每个 1 ≤ s ≤ N。 另请注意,一般来说, d(s,\ t) ≠ d(t,\ s).
我们将进一步定义 D 如下:
Snuke 正在构建 T' 这样 D 将是可能的最小值。 有多少种不同的构造方法 T' 这样 D 将是最小可能值,模 10^9 + 7?
约束
- 2 ≤ N ≤ 1000
- 1 ≤ a_i,\ b_i ≤ N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
输出
打印不同构造方式的数量 T' 这样 D 将是最小可能值,模 10^9 + 7.
示例输入 1
4 1 2 1 3 1 4
示例输出 1
2
的最小可能值 D is 1。 有两种构造方法 T' 达到这个值,如下图所示:

示例输入 2
4 1 2 2 3 3 4
示例输出 2
6
的最小可能值 D is 2。 有六种构造方法 T' 达到这个值,如下图所示:

示例输入 3
6 1 2 1 3 1 4 2 5 2 6
示例输出 3
14
示例输入 4
10 2 4 2 5 8 3 10 7 1 6 2 8 9 5 8 6 10 6
示例输出 4
102