Increase efficiency in a code I typed.

Question

I used this code to calculate (n+m-2)!/(n-1)!(m-1)! mod 1000000007
n,m could be up to 1000000
this should check for t test cases(t<=1000)
however this does not work fast enough
is there a any way I can make it more efficient
please don't tell me to read a page because I read many tutorials on how to increase efficiency
tell me directly how to fix

please help

import math

def f(x, y):
r = 1
for i in range(x, x + y - 1):
r *= i
return math.factorial(y - 1), r

t = 10 ** 9 + 7
for i0 in range(int(input().strip())):
n, m = tuple(map(int, input().strip().split()))
n, m = (n, m) if n > m else (m, n)
b, c = f(n, m)
print((c // b) % t)

Answer 1

You really should apply the modulo after each multiplication, as the computation time extends fast as the numbers grow.

Try this:

https://code.sololearn.com/ct5WgmDrixEC

#1st input: number of tests
#2nd+ input(s): n and m separated by a space
#Output: (n+m-2)!/((n-1)!(m-1)!) mod 10**9 + 7

#extended gcd and modinv functions from rosettacode.org
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m

#Product of terms between x and y, modulo t
def f(x, y, t):
r = 1
for i in range(x, y+1):
r = (r*i)%t
return r

t = 10 ** 9 + 7
for i in range(int(input().strip())):
n, m = tuple(map(int, input().strip().split()))
n, m = (n, m) if n > m else (m, n)
b, c = f(2, m-1, t), f(n, n+m-2, t)
print((c * modinv(b, t)) % t)

Answer 2

Jesus, Zen, you are a real ninja!

Answer 3

heya, what's the name of that hackerrank challenge?

Answer 4

matrix tracing
under mathematics>fundamentals

Answer 5

hey thank you very much for the help
☺