More Peaks More Fun

AtCoder

IDagc053_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "More Peaks More Fun",
    "description": {
      "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$. Find, mo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc053_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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, mo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments