ext_gcd_and_mod_inv.py

def gcd(a, b):
    if a == 0:return b
    else:return gcd(b % a, a)

#returns (x, y, gcd(a,b))  s.t. ax + by = gcd(a,b)
def ext_gcd(a, b):
    if a == 0:return (0, 1, b)
    else:
        (X, Y, g) = ext_gcd(b % a, a)
        return (Y-b//a*X, X, g)
        
MOD = 10**9 + 7
inv = [0] * 10000
inv[1] = 1

for i in range(2, 10000):
    inv[i] = MOD // i * -inv[MOD % i] % MOD

      
#check
print(all(x * ext_gcd(x, MOD)[0] % MOD == 1 for x in range(1, 10000)))
print(all(x * inv[x] % MOD == 1 for x in range(1, 10000)))


        

The code was written in https://youtu.be/eiJyDb9c3Js