You are given a binary tree with $n$ nodes numbered $1, 2, 3, \ldots, n$. The root of the tree is node $1$. Your task is to determine how many ways there are to pair connected nodes so that each node is paired up with at most one another node.

As the number of ways may be large, output the result modulo $10^9+7$.

Input

The first line of the input contains a single number, $n$, the number of nodes in the tree.

Next $n$ lines each contain two integers, $l_i$ and $r_i$, describing the left and right child of $i^{th}$ node. $l_i$ is the index of left child of $i^{th}$ node and $r_i$ is the index of right child of $i^{th}$ node. Index $0$ means that no node is connected as a child.

Output

A single line, result modulo $10^9+7$.

Limits

• $1 \le n \le 10^6$

Example

Input:

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

Output:

19

Explanation: