問題文
现在,在直线排列的方格上 n 有Poyokun,i (1 \leq i \leq n)第Poyokun是, 添加位于p_i 处的桩的长度 它与 l_i 链接。 换句话说, i th Poyokun 是 您可以在 p_i - l_i 假设一直下雨,直到 p_i + l_i 范围内(包括两端)自由移动。
当Poyoku君和他的朋友们按照下标的顺序从左到右分别位于不同的方格时,你能想到多少种放置方式? 换句话说,找到满足以下条件的弹出位置的可能组合的数量。 i (1 \leq i \leq n) 第 Poyokun 的位置 作为 x_i ,
当我们说位置的组合彼此不同时,我们的意思是至少有一个Poyoku-kun的位置不同。
答案将是一个非常大的值,所以 请回答除以1{,}000{,}000{,}007 后的余数。
入力
输入以以下格式给出。
n p_1 l_1 p_2 l_2 ... p_n l_n
- 1 行是一个整数,表示 Poyokun 的总数。 n (1 \leq n \leq 1,000)。
- 继续 一个整数,表示第 n 行包含 上线i 个 Poyokun 连接到的桩的位置。 p_i (0 \leq p_i \leq 1,000,000,000)和 一个整数,表示连接第i 个点的链的长度 当 l_i (0 \leq l_i \leq 1,000)。
- i \lt j 时,p_i \lt p_j 有保证。
出力
Poyokun 可能的配置总数。 除以 1,000,000,007 后的余数 1 行。
在末尾使用换行符,并且不要包含不必要的字符或空行。
入力例1
1 0 3
出力例1
7
Poyokun 可能的位置是:-3, -2, -1, 0, 1, 2, 3 的 7 是的。
入力例2
2 0 3 1 2
出力例2
20
Poyokun 可能的配置总数为 (1 Poyokun的位置, 2 位置),然后 (-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) 的 20 是的。