Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mr. Ant and His Problem

By Alim14 · Limits 1s, 512 MB

Mr. Ant has 3 boxes and the infinite number of marbles. Now he wants to know the number of ways he can put marbles in these three boxes when the following conditions hold.

  1. Each box must contain at least 1 marble.
  2. The summation of marbles of the 3 boxes must be in between X and Y inclusive.

Now you are given X and Y. You have to find the number of ways Mr. Ant can put marbles in the 3 boxes.

Input

Input starts with an integer T (1 ≤ T ≤ 1000000), denoting the number of test cases. Each test case contains two integers X and Y (1 ≤ X ≤ Y ≤ 1000000).

Output

For each test case, print the required answer modulo 1000000007.

Sample

InputOutput
1
4 5
9

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.

Discussion

Statistics


33% Solution Ratio

tahsynxEarliest, May '16

ashikurrahmanFastest, 0.0s

ashikurrahmanLightest, 4.7 MB

Valentin_EShortest, 999B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.