AT_agc053_e [AGC053E] More Peaks More Fun

有 $2N$ 张卡片和 $N$ 个盒子。卡片编号为 $1$ 到 $2N$，盒子编号为 $1$ 到 $N$。每个盒子里有 $2$ 张卡片。第 $i$ 个盒子里放着编号为 $A_i$ 和 $B_i$ 的卡片。 请计算有多少种将这 $N$ 个盒子排成一行的方法，使得满足以下条件的排列方案数（对 $10^9+7$ 取模）： - 按照从左到右的顺序依次打开盒子，并将其中的 $2$ 张卡片以任意顺序依次放到当前卡片序列的末尾，最终得到长度为 $2N$ 的卡片序列。记从左到右第 $j$ 张卡片的编号为 $P_j$。要求通过合理安排每个盒子中两张卡片的顺序，使得数列 $P_1,P_2,\ldots,P_{2N}$ 中的“峰值”个数恰好为 $N-1$。 这里，数列 $P_1,P_2,\ldots,P_{2N}$ 中的“峰值”指的是满足 $2\leq j

输入通过标准输入给出，格式如下： > $N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出满足条件的排列方案数。

## 限制 - $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$ 互不相同。 ## 样例解释 1 例如，将盒子 $1,2,3$ 按此顺序排列时，可以如下安排卡片顺序，使得数列 $P$ 的峰值个数为 $2$： - 首先将盒子 $1$ 中的卡片按 $1,3$ 的顺序放置。 - 然后将盒子 $2$ 中的卡片按 $2,4$ 的顺序放到末尾。 - 最后将盒子 $3$ 中的卡片按 $6,5$ 的顺序放到末尾。 此时，数列 $P$ 为 $(1,3,2,4,6,5)$，其中 $j=2,5$ 是峰值。 由 ChatGPT 4.1 翻译