Perfect Matchings
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

AAA gets a complete graph of 2n vertices, where every pair of distinct vertices is connected by a unique edge, as a birthday present. However, AAA thinks the complete graph is not that beautiful and he decides to delete 2n-1 edges that form a tree.

Now he wonders the number of different perfect matchings in the remaining graph. Note that a perfect matching is a set of n edges where no two edges share a common vertex. Since the answer may be very large, you only need to output the answer modulo .

输入描述:

The first line contains a single integer n .

Each of the next 2n-1 lines contains two integers u and v , representing an edge deleted from the complete graph. It is guaranteed that the given edges form a tree of 2n vertices.

输出描述:

Output a line containing a single integer, representing the answer modulo .
示例1

输入

复制
2
1 2
1 3
3 4

输出

复制
1
示例2

输入

复制
3
1 2
2 3
3 4
4 5
5 6

输出

复制
5