← 返回题目列表

AtCoder · icpc2013summer_day3_e

E. 排名

中文机器翻译题面 查看原题

伊库塔君居住的城镇 有N塔。 每座塔都从0开始。N-1给出不同的数字,并且数字i之塔 它被称为i。 伊库塔充满好奇。 我们对N塔的高度感兴趣,并且希望创建一个表格来显示它们的大小关系。 我决定制作T。 它有 T为N \times N元素,每个元素Ti, j (0 \leq i, j \leq N - 1)定义如下。

  • Ti, j = -1⇔ 塔iの高さが塔jの高さより小さい

  • Ti, j = 0 ⇔ 塔iの高さと塔jの高さが等しい

  • Ti, j = 1 ⇔ 塔iの高さが塔jの高さより大きい

伊库塔君登上了首页 创建T的研究是选择两座塔并比较它们的高度。 重复N-1次。

关于伊库塔君的调查,已知以下内容。

  • i第比较(1 \leq i \leq \ N - 1)塔 如果选择ai, 塔bi,则塔ai的高度是塔 它大于bi的高度。换句话说 这是Tai, bi = 1, Tbi, ai = -1。

  • 每个塔最多与较大的塔进行比较一次。

不幸的是,只有伊库塔君的研究信息可用。 并不总是能够唯一确定T的内容。 表T与Ikta的研究一致, 当存在定义T的塔高度组合时 让我们将正确的表称为T。 我希望 Ikta 计算出有多少个可能的正确表格并告诉我。

然而,虽然两个比较塔的高度彼此不同,但所有塔的高度不一定彼此不同。

输入

输入按以下格式给出。

N
a1 b1
...
aN-1 bN-1

N代表塔的数量。 ai, bi (1 \leq i \leq N - 1) 是一座塔ai是一座塔bi代表较高。

约束

输入中的每个变量都满足以下约束。

  • 1 \leq N \leq 200

  • 0 \leq ai, bi < N

  • ai \neq bi

  • 不同的塔可能具有相同的高度。

  • 伊库塔君的研究结果本身并不矛盾,而且至少有一张表格与伊库塔君的研究结果不矛盾。T存在。

输出

打印可能正确的表 T 的数量除以 1,000,000,007 的余数。

示例输入 1

3
0 1
1 2

样本输入 1 的输出

1
  • 正确的表格T是上面的图之一。

示例输入 2

3 
0 1
0 2 

样本输入 2 的输出

3
  • 正确的表格T有如上图所示的三种方式。

示例输入 3

1 

样本输入 3 的输出

1
  • 正确的表格T是上面的图之一。

示例输入 4

7
0 1
1 2
2 3
3 4
0 5
0 6

样本输入 4 的输出

91