F. Beavers and Revaebs
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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
4
1 1
2 2
3 3
10 10
Output
1
Input
1
1 2000
Output
2000
Input
4
1 2
1 2
1 2
1 2
Output
2
Input
5
1 3
2 4
1 4
1 2
3 3
Output
18
Input
6
1 5
1 5
1 5
1 5
1 5
1 5
Output
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.