캥거루

K 이사장은 캥거루에 관심을 갖고 캥거루의 행동을 관찰하기로 했다. 이사장은 $N$마리의 캥거루를 관찰하고 있다. 각 캥거루에게는 주머니가 하나씩 달려 있다. 캥거루에는 $1, 2, \ldots, N$의 번호가 붙어 있다. 캥거루 $i$의 몸통 크기는 $A_i$이고, 주머니 크기는 $B_i$이다. 주머니 크기는 몸통 크기보다 작다($A_i > B_i$).

처음에는 어떤 캥거루의 주머니 안에도 다른 캥거루가 없다. 캥거루들은 더 이상 할 수 없을 때까지 다음 작업을 반복한다.

$A_i < B_j$를 만족하는 캥거루 $i$, $j$의 쌍 가운데, 캥거루 $i$가 다른 캥거루의 주머니 안에 없고 캥거루 $j$의 주머니 안에 다른 캥거루가 없는 쌍이 있으면, 캥거루 $i$는 캥거루 $j$의 주머니 안으로 들어간다. 이때 캥거루 $i$의 주머니 안에 다른 캥거루가 있어도 되고, 캥거루 $j$가 다른 캥거루의 주머니 안에 있어도 된다. 그런 쌍이 여러 개 있으면 어느 쌍이 선택될지는 알 수 없다. 캥거루 $i$의 주머니 안에 다른 캥거루가 들어 있으면, 그 캥거루는 캥거루 $i$와 함께 움직인다.

주어진 몸통과 주머니 크기에 대해 최종 상태가 몇 가지인지 구하라. 답은 $10^9+7$(1,000,000,007)로 나눈 나머지로 구한다.

표준 입력에서 다음 입력을 읽어라.

첫째 줄에 정수 $N$이 주어진다. $N$은 캥거루의 마리 수이다.

이후 $N$개의 줄에는 $i+1$번째 줄에 정수 $A_i$, $B_i$가 공백으로 구분되어 주어진다. $A_i$는 $i$번째 캥거루의 몸통 크기, $B_i$는 $i$번째 캥거루의 주머니 크기이다.

최종 상태가 몇 가지인지 $10^9+7$로 나눈 나머지를 한 줄에 출력하라.

• $1 \le N \le 300$ (캥거루의 마리 수)
• $1 \le B_i < A_i \le 1000000000$ ($i$번째 캥거루의 주머니와 몸통 크기)
• 시간 제한 2000 ms, 메모리 제한 512 MB.