RIVALS  Rivals
Mohamed Yasser (AKA Abo3obaida) 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".
Abo3obaida replied: "I'll not lose this challenge".
Could you help Abo3obaida to figure out how many ways to the target?!
Since the required number may be very large, find its remainder of division by 1000000007 (10^{9} + 7).
Input
The first line of input contains an integer T (1 <= T <= 1000) followed by T test cases.
Each case contains two spaceseparated integers X, Y (0 <= X, Y <= 10^{6}).
Output
For each test case, print a single integer the answer to the problem modulo 1000000007 (10^{9} + 7).
Example
Input: 3 1 3 2 4 5 3 Output: 4 15 56
hide comments
shikhar_may7:
20191008 10:29:59
AC Finally ... Inverse Modulo and modular exponentiation 

aryan29:
20190124 07:19:07
I am getting run time error when I am storing factorials till 10^6 in an array are they entering test case with greater value than that Last edit: 20190124 07:51:17 

arthur_q:
20180628 17:10:13
Tip: a^1 mod (10^9 + 7) is the same as a^(10^9 + 7  2) mod (10^9+7) 

ayushgupta1997:
20180131 14:58:20
Good Problem :) 

praney_rai:
20170615 22:21:13
killer observation :D 

sonudoo:
20170129 16:32:58
Learned lot of things. Pascal triangle + Combinations using factorial. 

[Lakshman]:
20151026 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:
20150712 16:03:06
We have to use memoization to save the factorials upto 2*10^6 

JY:
20150526 10:30:21
At 0 0 , output is 1. 

eightnoteight:
20150122 14:23:15
after solving this question, try to solve this, NY10E

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