AT_agc053_e [AGC053E] More Peaks More Fun

[problemUrl]: https://atcoder.jp/contests/agc053/tasks/agc053_e $ 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 $ は相異なる。 ### Sample Explanation 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 $ がピークとなります。