D - ぽよぽよ 解説 /

実行時間制限: 2 sec / メモリ制限: 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

    1
0 3

    出力例1

    7

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

    入力例2

    2
0 3
1 2

    出力例2

    20

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