Kortos

A player is playing a card game. At the start she holds $N$ cards. Each card is described by a suit and a number, and all $N$ cards are distinct.

She builds a single pile. First she places any one card of her choice. After that, on each turn she may take a card still in her hand and place it on top of the current top card, provided the new card is either:

• the same number as the current top card, or
• the same suit as the current top card and has a strictly greater number.

For example, if the current top card has suit $1$ and number $4$, she may place a card with number $4$ (of any suit), or a card of suit $1$ whose number is greater than $4$; she may not place a card of suit $1$ with number $3$, nor a card of a different suit whose number is not $4$.

After placing the first card she may stop at any time.

Count how many different final piles are possible. Two piles are different if the cards they contain differ, or the cards are the same but their order differs. Because the answer can be large, output it modulo $1,000,000,007$.

The first line contains a single integer $N$ — the number of cards in hand at the start.

Each of the next $N$ lines contains two space-separated integers $a_i$ and $b_i$ — the suit and the number of the $i$-th card.

Output a single integer — the number of different possible final piles, taken modulo $1,000,000,007$.

• $3 \le N \le 1,000,000$
• $1 \le a_i, b_i \le N$