ANTP - Mr. Ant & His Problem

no tags 

 

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, denoting the number of test cases. Each test case contains two integers X and Y.

Constraints

1<=T<=1000000

1<=X<= Y<=1000000

Output

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

Sample Input

Sample Output

1

4 5

9

Explanation for the first test case


1 1 2

Way 01

1 1 3

Way 02

1 2 1

Way 03

1 3 1

Way 04

2 1 1

Way 05

3 1 1

Way 06

1 2 2

Way 07

2 1 2

Way 08

2 2 1

Way 09

Note: use faster i/o method.

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology


hide comments
nimphy: 2018-04-29 04:39:46

I want to know FFT is ok?

Sidharth Sikri: 2016-08-14 15:37:20

can someone tell me, why am i getting a WA for my code -- http://ideone.com/4POTiA
my code passes the sample test case and also the test cases given here by @nhari

nhari: 2016-05-21 18:18:47

5
2 10
5 26
23 59
100 500
30 89
answers are:
120
2596
30969
20551651
109910

lalit_nit2: 2016-04-11 00:18:02

intersting but irritating ..(^_^)

Jitesh: 2016-04-03 16:50:44

@aqua_regia. answer will be 0.

aqua_regia: 2016-04-03 10:57:58

Are there any special test cases. What if x=1 y=2 ? Is the answer 0 or 1. And provide some additional test cases.


Added by:Alim
Date:2016-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem