D - ぽよぽよ

Contest Duration: 2014-11-09(Sun) 00:00 - 2014-11-09(Sun) 01:30 (local time) (90 minutes)

D - ぽよぽよ Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

今、直線上に並んだマスの上に $n$ 匹のぽよくんが存在しており、 $i$ ( $1 \leq i \leq n$ ) 番目のぽよくんは、 $p_i$ の位置にある杭に長さ $l_i$ の鎖で繋がれています。
つまり、 $i$ 番目のぽよくんは $p_i - l_i$ から $p_i + l_i$ の範囲（両端を含む）のマスを自由に動くことができます。

ぽよくんが添字の順に左からそれぞれ異なるマスにいるとき、ぽよくん達の配置は何通り考えられますか。
つまり、次の条件をみたすぽよくんの位置の組み合わせとして考えられる場合の数を求めてください。
$i$ ( $1 \leq i \leq n$ ) 番目のぽよくんの位置を $x_i$ として、

$x_i$ は整数

$p_i - l_i \leq x_i \leq p_i + l_i$

どのような $j$ ( $1 \leq j \leq n$ ) についても、 $i \lt j$ であるならば、 $x_i \lt x_j$ となっている

位置の組み合わせが互いに異なるとは、少なくともどれか一匹のぽよくんについて、位置が異なることだとします。

答えは非常に大きな値になるので、 $1{,}000{,}000{,}007$ で割った余りを答えてください。

入力

入力は以下の形式で与えられる。

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

$1$ 行目には、ぽよくんの総数を表す整数 $n$ ( $1 \leq n \leq 1,000$ ) が与えられる。
続く $n$ 行には、 $i$ 番目のぽよくんが繋がれている杭の位置を表す整数 $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$ であることが保証されている。

出力

ぽよくんの可能な配置の総数を $1,000,000,007$ で割った余りを $1$ 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

Copy

1
0 3

1
0 3

出力例1

Copy

ぽよくんの可能な配置は、 $-3$ , $-2$ , $-1$ , $0$ , $1$ , $2$ , $3$ の $7$ 通りです。

入力例2

Copy

2
0 3
1 2

2
0 3
1 2

出力例2

Copy

ぽよくんの可能な配置の総数は、( $1$ 番目のぽよくんの位置, $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$ 通りです。