Problem Statement

We have $2N$ cards and $N$ boxes. The cards are numbered $1$ through $2N$, and the boxes are numbered $1$ through $N$. Each box contains two cards; Box $i$ contains Card $A_i$ and Card $B_i$.

Find, modulo $(10^9+7)$, the number of ways to arrange the $N$ boxes in a row that satisfies the following condition.

• Consider getting a sequence of $2N$ cards as follows: for each box, from left to right, open it and append the two cards in it to the end of the sequence in an order we like. In this way, it is possible to get a sequence $P_1,P_2,\ldots, P_{2N}$ with $N-1$ peaks.

Here, a peak in a sequence $P_1,P_2,\ldots, P_{2N}$ is an integer $j$ satisfying $2 \leq j < 2N$ such that $P_{j-1} < P_j$ and $P_j > P_{j+1}$.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i, B_i \leq 2N$
• $A_1,\ldots,A_N,B_1,\ldots,B_N$ are pairwise distinct.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_N B_N

Output

Print the answer.