CF251E.Tree and Table

Little Petya likes trees a lot. Recently his mother has presented him a tree with 2_n_ nodes. Petya immediately decided to place this tree on a rectangular table consisting of 2 rows and n columns so as to fulfill the following conditions:

1. Each cell of the table corresponds to exactly one tree node and vice versa, each tree node corresponds to exactly one table cell.
2. If two tree nodes are connected by an edge, then the corresponding cells have a common side.

Now Petya wonders how many ways are there to place his tree on the table. He calls two placements distinct if there is a tree node which corresponds to distinct table cells in these two placements. Since large numbers can scare Petya, print the answer modulo 1000000007 (109 + 7).

小Petya非常喜欢树。最近，他妈妈送给他一棵含有 $2n$ 个节点的树。Petya立刻决定将这棵树放置在一个由 $2$ 行 $n$ 列组成的矩形表格上，使得满足以下条件：

1. 表格中的每个单元格恰好对应树中的一个节点，反之，树中的每个节点也恰好对应表格中的一个单元格。
2. 若树中两个节点之间存在一条边，则它们所对应的表格单元格必须具有公共边（即上下或左右相邻）。

现在Petya想知道：有多少种不同的方式可以将这棵树放置在表格上？若存在某个树节点，在两种放置方案中对应于表格中不同的单元格，则称这两种放置方案是不同的。由于大数可能吓到Petya，请将答案对 $1000000007$（即 $10^9 + 7$）取模后输出。

The first line contains a single integer n (1 ≤ n ≤ 105). Next (2_n_ - 1) lines contain two integers each a__i and b__i (1 ≤ a__i, b__i ≤ 2_n_; a__i ≠ b__i) that determine the numbers of the vertices connected by the corresponding edge.

Consider the tree vertexes numbered by integers from 1 to 2_n_. It is guaranteed that the graph given in the input is a tree, that is, a connected acyclic undirected graph.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。接下来的 $(2n - 1)$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 2n$；$a_i \neq b_i$），表示由对应边连接的两个顶点的编号。

考虑一棵顶点编号为 $1$ 到 $2n$ 的树。输入所给图保证是一棵树，即一个连通的无环无向图。

Print a single integer — the required number of ways to place the tree on the table modulo 1000000007 (109 + 7).

输出一个整数——将树放置在桌子上的方案数对 $1000000007$（即 $10^9 + 7$）取模的结果。

Note to the first sample (all 12 variants to place the tree on the table are given below):

1-3-2 2-3-1 5 4 6 6 4 5
| | | | | | | | | | | |
5 4 6 6 4 5 1-3-2 2-3-1

4-3-2 2-3-4 5-1 6 6 1-5
| | | | | | | |
5-1 6 6 1-5 4-3-2 2-3-4

1-3-4 4-3-1 5 2-6 6-2 5
| | | | | | | |
5 2-6 6-2 5 1-3-4 4-3-1

第一个样例的说明（下方列出了将树放置在桌面上的所有 12 种方案）：

1-3-2 2-3-1 5 4 6 6 4 5
| | | | | | | | | | | |
5 4 6 6 4 5 1-3-2 2-3-1

4-3-2 2-3-4 5-1 6 6 1-5
| | | | | | | |
5-1 6 6 1-5 4-3-2 2-3-4

1-3-4 4-3-1 5 2-6 6-2 5
| | | | | | | |
5 2-6 6-2 5 1-3-4 4-3-1