問題文

ぬけす君はダンスプログラミングの祭典「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

4
1 3
3 7
4 7
3141592 3141592

出力例 1

6
21
14
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 通りあります。