伊库塔君居住的城镇 有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