小Petya非常喜欢树。最近,他的母亲送给他一棵有 2n 个节点的树。 Petya立即决定将这棵树放在一个由2行n列组成的矩形桌子上,以满足以下条件:
1. 表的每个单元格恰好对应一个树节点,反之亦然,每个树节点恰好对应一个表单元格。
2. 如果两个树节点通过边连接,则相应的单元具有公共边。
现在 Petya 想知道有多少种方法可以把他的树放在桌子上。如果存在一个树节点对应于这两个放置中不同的表单元格,则他将这两个放置称为不同的放置。由于大数字可能会吓到 Petya,因此请打印对 1000000007 (109 + 7) 取模的答案。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105)。接下来 (2n - 1) 行包含两个整数,每个 ai 和 bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi),它们确定由相应边连接的顶点的数量。
考虑用 1 到 2n 的整数编号的树顶点。保证输入中给出的图是一棵树,即连通的无环无向图。
输出
打印一个整数 — 将树放置在表上所需的方式数以 1000000007 (109 + 7) 为模。
示例
输入 #1
3 1 3 2 3 4 3 5 1 6 2
输出 #1
12
输入 #2
4 1 2 2 3 3 4 4 5 5 6 6 7 7 8
输出 #2
28
输入 #3
2 1 2 3 2 4 2
输出 #3
0
注意
第一个示例的注释(下面给出了将树放置在桌子上的所有 12 种变体):