In programming contests, beavers solve problems in order, from first to last. Revaebs, on the other hand, are a special type of rodent that solve problems in reverse order, from last to first.

$N$ beavers and $N$ revaebs will compete against each other in the upcoming programming contest! The contest consists of $N$ problems, the $k^{\text{th}}$ problem having an integer point value $p_k$ between $l_k$ and $r_k$, inclusive. A contestant's score is the sum of the point values of the problems they solve.

On contest day, it is known that the $i^{\text{th}}$ beaver solved the first $i$ problems, and the $j^{\text{th}}$ revaeb solved the last $j$ problems. Additionally, the only pair of contestants with the same score are the two that solved all problems, the $N^{\text{th}}$ beaver and the $N^{\text{th}}$ revaeb. Given this information, count the number of possible assignments of points values to the problems in the contest. Since this number might be large, output its remainder when divided by $10^9 + 7$.

Input

The first line contains $N$ ($1 \leq N \leq 50$), the number of problems in the contest.

$N$ lines follow. The $k^{\text{th}}$ of these lines contains two space-separated integers, $l_k$ and $r_k$ ($1 \le l_k \le r_k \le 2000$).

Output

Output one line containing the answer: the number of sequences of point values modulo $10^9+7$.

Scoring

• ($10$ points) $N \leq 8$ and $r_k \leq 8$ for all $k$.
• ($30$ points) $l_k = 1$ for all $k$ and there exists a fixed $R$ such that $r_k = R$ for all $k$.
• ($30$ points) $r_k \leq 100$ for all $k$.
• ($30$ points) No additional constraints.

Examples

Input 1

4
1 1
2 2
3 3
10 10

Output 1

1

Input 2

1
1 2000

Output 2

2000

Input 3

4
1 2
1 2
1 2
1 2

Output 3

2

Input 4

5
1 3
2 4
1 4
1 2
3 3

Output 4

18

Input 5

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

Output 5

5120

Note

Sample Explanation 1

The point values of the problems can only be $1, 2, 3, 10$. Using these point values, the scores of the beavers are $1, 3, 6, 16$ respectively and the scores of the revaebs are $10, 13, 15, 16$ respectively. All of these are different other than the score of $16$ attained by the $4^{\text{th}}$ beaver and revaeb, so this one sequence is valid, making the answer $1$.

Sample Explanation 2

This sample satisfies the constraints for the second subtask.

Sample Explanation 3

This sample satisfies the constraints for the second subtask.

The only valid sequences of point values are $1, 2, 2, 2$ and $2, 2, 2, 1$, making the answer $2$.

Sample Explanation 5

This sample satisfies the constraints for the second subtask.