VECTAR7 - Number of score sequences

no tags 

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.


hide comments
smso: 2019-06-28 09:13:59

Use spojtoolkit for 1st case of ending.
For 2nd case:
answer is 603457371LL for 24:24
build other answers from 24:24

Sushovan Sen: 2017-03-24 08:49:51

All corner cases covered. Nice question...

Siddharth Singh: 2016-07-21 10:36:23

my solution seems correct but the only problem i'm having is finding nCr till 10^9 :(

------------------------------------------------------------------------------------------------
Changed my approach and AC in 2nd go <3
Beware of the corner cases. it costed me the first WA .

Last edit: 2016-07-21 18:24:38
Jitesh: 2016-07-14 15:34:26

Nice Problem. (Y)

akash180805: 2016-07-06 18:49:57

@piyush Can u plz provide me the outputs for test cases: 27 25,28 26 && 28 25

Re: Answer for 25:27 is 206914735. No more test cases will be provided. Best of luck :)

Last edit: 2016-07-06 19:23:10
akash180805: 2016-07-06 17:20:00

@piyush Getting repeated WA.can u plz provide me a sample test case where my solution is wrong.Plz check my last submission.

Re: You have WA for all the cases where both the scores are not less than 25. Check those.

Last edit: 2016-07-06 17:29:04
akash180805: 2016-07-06 10:23:35

@piyush plz check my last submission why m i getting WA.Have i missed any critical test cases???

Re: You have covered all corner cases, except one. Also, your solution is incorrect for other normal cases.

Last edit: 2016-07-06 10:29:55
Vipul Srivastava: 2016-07-06 08:05:59

Loved solving this... Nice question..!!

deadbrain: 2016-07-05 16:39:07

@piyush : getting repeated WA. Please check my last submission.

Re:Your solution is wrong. You have got all the corner cases right, but your actual solution works only for sample test case and corner cases and none other. Correct your solution.

Last edit: 2016-07-05 16:49:24
pvsmpraveen: 2016-07-04 21:54:14

I have done a silly Mistake :P
Finally AC!


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