RIVALS - Rivals

no tags 

Mohamed Yasser (AKA Abo-3obaida) and Mohamed Ahmed (AKA Nesr) pretend to be rivals, the two clearly have a deep and understanding friendship.

One day they imagine that the city is a 2D plane with Cartesian coordinate system, the two rivals are located in point (0, 0), and they are targeting point (X, Y).

They can make two moves only:

  1. move right to the point (X + 1, Y).
  2. move up to the point (X, Y + 1).

Nesr immediately said: "I've figured out how many ways are there to reach our target".
Abo-3obaida replied: "I'll not lose this challenge".

Could you help Abo-3obaida to figure out how many ways to the target?!

Since the required number may be very large, find its remainder of division by 1000000007 (109 + 7).

Input

The first line of input contains an integer T (1 <= T <= 1000) followed by T test cases.

Each case contains two space-separated integers  X,  Y (0 <= X, Y <= 106).

Output

For each test case, print a single integer the answer to the problem modulo 1000000007 (109 + 7).

Example

Input:
3
1 3
2 4
5 3

Output:
4
15
56

hide comments
[Lakshman]: 2015-10-26 04:41:59

@ANKIT KUMAR have you lost your mind? Why are giving the link of solution. ADMIN please take some action and remove all links posted by this user.

Shashank Tiwari: 2015-07-12 16:03:06

We have to use memoization to save the factorials upto 2*10^6

JY: 2015-05-26 10:30:21

At 0 0 , output is 1.

eightnoteight: 2015-01-22 14:23:15

after solving this question, try to solve this, NY10E
PS: this is a spoiler to NY10E, but you would notice that we can think of this problem in that way too !

bourne: 2014-11-27 20:15:36

@Author - what would be the answer to
0 0 ?
Is it 0 or 1?

Later -> Got it After 2 WAs. I would suggest the author to add this case to the question/test cases.

Last edit: 2014-11-27 20:35:09
abdou_93: 2014-11-25 21:23:43

@Min_25 .again the best one (Y) :D


Added by:eagle93
Date:2014-11-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64