E - More Peaks More Fun Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

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 < 2N なる整数 j であって P_{j-1} < P_j かつ P_j > P_{j+1} となるものを指します。

制約

  • 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 は相異なる。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
:
A_N B_N

出力

答えを出力せよ。

入力例 1

3
1 3
2 4
5 6

出力例 1

4

例えば、箱 1,2,3 をこの順で並べたとき、 以下のようにカードを並べることで、数列 P のピークの個数が 2 となります。

  • まず箱 1 に入っているカードをカード 1,3 の順で並べる。
  • 次に箱 2 に入っているカードをカード 2,4 の順で末尾に並べる。
  • 最後に箱 3 に入っているカードをカード 6,5 の順で末尾に並べる。

このとき、数列 P は (1,3,2,4,6,5) となり j=2,5 がピークとなります。

入力例 2

6
5 8
7 2
1 3
11 6
4 12
9 10

出力例 2

492

入力例 3

10
20 15
8 5
6 7
4 9
13 1
11 14
10 17
19 12
3 16
2 18

出力例 3

1411200

Score : 1400 points

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.

Sample Input 1

3
1 3
2 4
5 6

Sample Output 1

4

For 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:

  • first, arrange the cards in Box 1 in the order 1, 3;
  • next, append the cards in Box 2 at the end in the order 2, 4;
  • lastly, append the cards in Box 3 at the end in the order 6, 5.

Here, we have P=(1,3,2,4,6,5) with peaks j=2,5.

Sample Input 2

6
5 8
7 2
1 3
11 6
4 12
9 10

Sample Output 2

492

Sample Input 3

10
20 15
8 5
6 7
4 9
13 1
11 14
10 17
19 12
3 16
2 18

Sample Output 3

1411200