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
sk128: 2021-07-29 07:55:21

Precomputation helped to overcome TLE :)

kumar_anubhav: 2020-06-11 21:42:50

Firstly Applied other algorithm and then realized this is not always true.... AC finally !!Fermat theorem rocks !!!

dkkv0000: 2020-04-01 10:04:45

@shikhar_may7 any resource for solving this kind of problem

pulkithb: 2019-12-16 08:47:08

nice question :)

Last edit: 2019-12-16 09:01:36
shikhar_may7: 2019-10-08 10:29:59

AC Finally ... Inverse Modulo and modular exponentiation

aryan29: 2019-01-24 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: 2019-01-24 07:51:17
arthur_q: 2018-06-28 17:10:13

Tip: a^-1 mod (10^9 + 7) is the same as a^(10^9 + 7 - 2) mod (10^9+7)

ayushgupta1997: 2018-01-31 14:58:20

Good Problem :)

praney_rai: 2017-06-15 22:21:13

killer observation :D

sonudoo: 2017-01-29 16:32:58

Learned lot of things. Pascal triangle + Combinations using factorial.


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