Kortos

한 플레이어가 카드 게임을 한다. 처음에 플레이어는 카드 $N$장을 손에 들고 있다. 각 카드는 무늬와 숫자로 정해지며, $N$장의 카드는 모두 서로 다르다.

플레이어는 카드를 한 무더기로 쌓는다. 먼저 원하는 카드 한 장을 내려놓는다. 그다음부터는 매 차례마다 손에 남아 있는 카드 중 하나를 현재 맨 위 카드 위에 올려놓을 수 있는데, 새로 올리는 카드는 다음 두 조건 중 하나를 만족해야 한다.

• 현재 맨 위 카드와 숫자가 같다, 또는
• 현재 맨 위 카드와 무늬가 같으면서 숫자가 더 크다.

예를 들어 현재 맨 위 카드의 무늬가 $1$, 숫자가 $4$라면, 숫자가 $4$인 카드(무늬는 무관)나 무늬가 $1$이면서 숫자가 $4$보다 큰 카드를 올릴 수 있다. 반대로 무늬가 $1$이고 숫자가 $3$인 카드나, 무늬가 다르면서 숫자가 $4$가 아닌 카드는 올릴 수 없다.

첫 카드를 내려놓은 뒤에는 언제든지 게임을 끝낼 수 있다.

만들 수 있는 서로 다른 최종 무더기가 몇 가지인지 구하라. 두 무더기는 포함된 카드가 다르거나, 카드는 같더라도 순서가 다르면 서로 다른 것으로 본다. 답이 커질 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $N$ — 처음에 손에 들고 있는 카드의 수가 주어진다.

이어지는 $N$개의 줄에는 각각 공백으로 구분된 두 정수 $a_i$와 $b_i$ — $i$번째 카드의 무늬와 숫자가 주어진다.

서로 다른 최종 무더기의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.

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