Problem Description

Currently, there are $ n $ Poyo-kuns located on squares arranged in a straight line, and the $ i $ ($1 \leq i \leq n$) Poyo-kun is chained to a peg at position $ p_i $ with a chain of length $ l_i $. This means that the $ i $ Poyo-kun can freely move within the range from $ p_i - l_i $ to $ p_i + l_i $ (inclusive).

How many possible arrangements are there for the Poyo-kuns when they are each in different squares from left to right in the index order? In other words, find the number of possible combinations of positions for the Poyo-kuns that satisfy the following conditions, where the position of the $ i $ Poyo-kun is denoted as $ x_i $:

1. $ x_i $ is an integer
2. $p_i - l_i \leq x_i \leq p_i + l_i$
3. For any $ j $ ($1 \leq j \leq n$), if $ i < j $, then $ x_i < x_j $

The combinations of positions are considered different if at least one Poyo-kun is in a different position.

Since the answer can be very large, output it modulo $ 1,000,000,007 $.

Input Format

The input is given in the following format:

$ n $ $ p_1 $ $ l_1 $ $ p_2 $ $ l_2 $ $ ... $ $ p_n $ $ l_n $

• The first line contains an integer $ n $ ($1 \leq n \leq 1,000$), representing the total number of Poyo-kuns.
• The following $ n $ lines contain an integer $ p_i $ ($0 \leq p_i \leq 1,000,000,000$), representing the position of the peg to which the $ i $ Poyo-kun is chained, and an integer $ l_i $ ($0 \leq l_i \leq 1,000$), representing the length of the chain for the $ i $ Poyo-kun.
• It is guaranteed that $ p_i < p_j $ when $ i < j $.

Output Format

Output the total number of possible arrangements of the Poyo-kuns modulo $ 1,000,000,007 $ in one line.

End with a newline and do not include any extra characters or blank lines.

Sample Input and Output

Sample Input #1

1
0 3

Sample Output #1

7

Sample Input #2

2
0 3
1 2

Sample Output #2

20

Notes/Hints

Sample Explanation 1

The possible positions for the Poyo-kun are $ -3 $, $ -2 $, $ -1 $, $ 0 $, $ 1 $, $ 2 $, and $ 3 $, totaling $ 7 $ possibilities.

Sample Explanation 2

The total number of possible arrangements for the Poyo-kuns, considering the positions of the first and second Poyo-kuns, are $ (-3, -1) $, $ (-3, 0) $, $ (-3, 1) $, $ (-3, 2) $, $ (-3, 3) $, $ (-2, -1) $, $ (-2, 0) $, $ (-2, 1) $, $ (-2, 2) $, $ (-2, 3) $, $ (-1, 0) $, $ (-1, 1) $, $ (-1, 2) $, $ (-1, 3) $, $ (0, 1) $, $ (0, 2) $, $ (0, 3) $, $ (1, 2) $, $ (1, 3) $, $ (2, 3) $, totaling $ 20 $ possibilities.

见题面 Input 部分

见题面 Output 部分