AT_pakencamp_2018_day3_f ミックスジュース

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_f ぬけす君はダンスプログラミングの祭典「KACoder」に出場するために、予選までの $ Q $ 日間、体にいいとされる妖精のミックスジュースを飲むことにしました。 妖精 $ 1 $ 羽の「美味しさ」は正の整数で表され、ミックスジュースの「美味しさ」は原料となった妖精の美味しさの合計です。 あなたは $ i $ 日目の朝に $ A_i $ 以上 $ B_i $ 以下の整数の美味しさの妖精をそれぞれ $ 1 $ 羽ずつ仕入れ、$ 1 $ 羽以上を選んでミキサーにかけます。なお鮮度の観点から、使わなかった妖精はその日の夜に廃棄し、以後使うことはありません。 このとき、$ i $ 日目に作るミックスジュースの美味しさとしてあり得る値は何通りあるでしょうか。答えは非常に大きくなる可能性があるため、$ 10^9+7 $ で割ったあまりを答えて下さい。

入力は標準入力より以下のように与えられます。 > $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ... $ A_Q $ $ B_Q $ - $ 1 $ 行目には、予選までの日数 $ Q $ が与えられます。 - $ 2 $ 行目から $ Q $ 行に渡って、$ i+1 $ 行目には $ i $ 日目の朝に仕入れる妖精の情報 $ A_i,\ B_i $ が与えられます。

全部で $ Q $ 行出力してください。 $ i $ 行目には、$ i $ 番目の質問に対する解答を出力してください。

### 制約 - $ 1\ \leq\ Q\ \leq\ 100000 $ - $ 1\ \leq\ A_i\ \leq\ B_i\ \leq\ 10^{9} $ - 入力は全て整数 ### 小課題 小課題 $ 1 $ \[$ 7 $ 点\] - $ Q\ =\ 1 $ を満たす。 - $ B_1\ -\ A_1\ \leq\ 20 $ を満たす。 小課題 $ 2 $ \[$ 60 $ 点\] - $ B_i\ -\ A_i $ の合計は $ 10^6 $ を超えない。 小課題 $ 3 $ \[$ 33 $ 点\] - 追加の制約はない。 ### Sample Explanation 1 例えば、$ 3 $ 日目の妖精の美味しさは $ 4,\ 5,\ 6,\ 7 $ です。そのうち $ 1 $ 個以上選ぶ方法は $ 15 $ 通りあり、ミックスジュースの美味しさはそれぞれ - $ 4,\ 5,\ 6,\ 7,\ 4+5,\ 4+6,\ 5+6,\ 4+7,\ 5+7,\ 6+7,\ 4+5+6,\ 4+5+7,\ 4+6+7,\ 5+6+7,\ 4+5+6+7 $ ですが、そのうち $ 5+6 $ と $ 4+7 $ だけ $ 11 $ と同じ値になっているので、美味しさとしてありうる値は $ 14 $ 通りあります。