RIVALS - Rivals
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:
- move right to the point (X + 1, Y).
- 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 |
RSS