Here comes our favorite, Saul Goodman! He was given a case, to rescue a guy from a court case who was accused of multiple crimes. As we know, There is no better place to go other than Saul Goodman.
"Did you not plan for this contingency? I mean the Starship Enterprise had a self-destruct button. I'm just saying."
Now, Saul is a master at his work. So he was offered a lot of cash. There were only 2 types of notes in the suitcase, 50$ & 100$ notes. n notes of 50$ and m notes of 100$ are available.
Saul had infinite number of different boxes to store his cash. The boxes were labelled 1,2,3,4.... and so on. The labels signified the capacity of the boxes. e.g. a box with capacity 1 can hold only 1 note, a box with capacity 2 can hold only 2 notes, and so on. To avoid mixing, Saul wants to keep only one type of note in each box, i.e a box with label 3 can contain either 3 50$ notes or 3 100$ notes.
Saul starts filling the boxes with the box labelled as 1 and continues the process of filling the boxes with cash & he can't skip over any box. He needs to maximize the number of filled boxes. Help him in finding the number of ways to do that.
INPUT:
First line contains an integer T denoting the number of test case(s). T lines follows, each containing two space separated integers n and m.
OUTPUT:
For each test case output the answer modulo 109+7 in separate line.
CONSTRAINTS
- 1 ≤ T ≤ 10
- 0 ≤ n,m ≤ 104
- m+n>=1
There are 4 50$ notes, 6 100$ notes. Boxes are 1,2,3,4...
There are two possible ways-
- In 1st box, Saul puts 1 50$ notes, In 2nd box he puts 2 100$ notes, In 3rd box he puts 3 50$ notes & in 4th he puts 4 100$ notes.
- In 1st box, Saul puts 1 100$ notes, In 2nd box he puts 2 100$ notes, In 3rd box he puts 3 100$ notes & in 4th he puts 4 50$ notes.
So the answer is 2.
