프로그래밍 대회에서 비버(beaver)들은 첫 번째 문제부터 마지막 문제까지 순서대로 문제를 해결합니다. 반면, 레바브(revaeb)는 마지막 문제부터 첫 번째 문제까지 역순으로 문제를 해결하는 특별한 설치류입니다.

$N$ 마리의 비버와 $N$ 마리의 레바브가 다가오는 프로그래밍 대회에서 서로 경쟁합니다! 대회는 $N$ 개의 문제로 구성되어 있으며, $k$ 번째 문제의 배점 $p_k$는 $l_k$ 이상 $r_k$ 이하의 정수입니다. 참가자의 점수는 자신이 해결한 문제들의 배점 합입니다.

대회 당일, $i$ 번째 비버는 첫 $i$ 개의 문제를 해결했고, $j$ 번째 레바브는 마지막 $j$ 개의 문제를 해결했다고 알려져 있습니다. 또한, 모든 문제를 해결한 $N$ 번째 비버와 $N$ 번째 레바브를 제외하고는 같은 점수를 가진 참가자 쌍이 존재하지 않습니다. 이 정보를 바탕으로, 대회 문제들의 배점을 정하는 가능한 경우의 수를 구하십시오. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하십시오.

입력

첫 번째 줄에는 대회의 문제 수 $N$ ($1 \leq N \leq 50$)이 주어집니다.

이어지는 $N$ 개의 줄에는 각 문제의 배점 범위 $l_k$와 $r_k$ ($1 \le l_k \le r_k \le 2000$)가 공백으로 구분되어 주어집니다.

출력

문제들의 배점 수열이 가능한 경우의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력하십시오.

서브태스크

• ($10$ 점) $N \leq 8$ 이고 모든 $k$ 에 대해 $r_k \leq 8$.
• ($30$ 점) 모든 $k$ 에 대해 $l_k = 1$ 이고, 모든 $k$ 에 대해 $r_k = R$ 인 고정된 $R$ 이 존재함.
• ($30$ 점) 모든 $k$ 에 대해 $r_k \leq 100$.
• ($30$ 점) 추가 제약 없음.

예제

입력 1

4
1 1
2 2
3 3
10 10

출력 1

1

입력 2

1
1 2000

출력 2

2000

입력 3

4
1 2
1 2
1 2
1 2

출력 3

2

입력 4

5
1 3
2 4
1 4
1 2
3 3

출력 4

18

입력 5

6
1 5
1 5
1 5
1 5
1 5
1 5

출력 5

5120

참고

예제 설명 1

문제들의 배점은 $1, 2, 3, 10$일 수밖에 없습니다. 이 배점을 사용하면 비버들의 점수는 각각 $1, 3, 6, 16$이 되고, 레바브들의 점수는 각각 $10, 13, 15, 16$이 됩니다. $4$ 번째 비버와 레바브가 얻은 점수 $16$을 제외하면 모두 다른 점수를 가지므로, 이 수열은 유효하며 정답은 $1$입니다.

예제 설명 2

이 예제는 두 번째 서브태스크의 제약을 만족합니다.

예제 설명 3

이 예제는 두 번째 서브태스크의 제약을 만족합니다.

가능한 유효한 배점 수열은 $1, 2, 2, 2$와 $2, 2, 2, 1$뿐이므로 정답은 $2$입니다.

예제 설명 5

이 예제는 두 번째 서브태스크의 제약을 만족합니다.