{"raw_statement":[{"iden":"problem statement","content":"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$.\nFind, modulo $(10^9+7)$, the number of ways to arrange the $N$ boxes in a row that satisfies the following condition.\n\n*   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.\n\nHere, 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}$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq A_i, B_i \\leq 2N$\n*   $A_1,\\ldots,A_N,B_1,\\ldots,B_N$ are pairwise distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$:$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3\n1 3\n2 4\n5 6"},{"iden":"sample output 1","content":"4\n\nFor example, if we arrange Boxes $1, 2, 3$ in this order, we can arrange the cards as follows to get a sequence $P$ with $2$ peaks:\n\n*   first, arrange the cards in Box $1$ in the order $1, 3$;\n*   next, append the cards in Box $2$ at the end in the order $2, 4$;\n*   lastly, append the cards in Box $3$ at the end in the order $6, 5$.\n\nHere, we have $P=(1,3,2,4,6,5)$ with peaks $j=2,5$."},{"iden":"sample input 2","content":"6\n5 8\n7 2\n1 3\n11 6\n4 12\n9 10"},{"iden":"sample output 2","content":"492"},{"iden":"sample input 3","content":"10\n20 15\n8 5\n6 7\n4 9\n13 1\n11 14\n10 17\n19 12\n3 16\n2 18"},{"iden":"sample output 3","content":"1411200"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}