VECTAR7 - Number of score sequences

Changu and Mangu were playing volleyball when they were handed a very easy question about the game. You can help them solve it.

In volleyball 2 teams play with initial score 0 and each team gets points which increases their scores by 1.

The game ends when: one of the teams gets 25 points and another team has < 24 points (strictly less than 24). If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.

Given the final score of a game (A B) i.e., the first team has scored A points and the second has scored B points, You have to find the number of different sequences of getting points by teams that leads to this final score?

Input

The first line contains the number of test cases T. The next T lines contain two integers A and B.

Output

Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 109 + 7, output the number modulo 109 + 7. Print 0 if no such volleyball game ends with the given score.

Example

Input:
2
3 25
24 17

Output:
2925
0

Constraints

T <= 15

0 ≤ A, B ≤ 109.


Added by:Piyush Kumar
Date:2016-07-04
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Hackerrank

hide comments
2016-07-04 21:01:32 Jacob Plachta
First line of the sample input should be 2 instead of 1

Re: Corrected. Thanks :)

Last edit: 2016-07-04 21:33:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.