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:
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).
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).
For each test case, print a single integer the answer to the problem modulo 1000000007 (109 + 7).
Input: 3 1 3 2 4 5 3 Output: 4 15 56
AC Finally ... Inverse Modulo and modular exponentiation
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 thatLast edit: 2019-01-24 07:51:17
Tip: a^-1 mod (10^9 + 7) is the same as a^(10^9 + 7 - 2) mod (10^9+7)
Good Problem :)
killer observation :D
Learned lot of things. Pascal triangle + Combinations using factorial.
@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.
We have to use memoization to save the factorials upto 2*10^6
At 0 0 , output is 1.
after solving this question, try to solve this, NY10E