def extended_euclidean(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = extended_euclidean(b % a, a)
        return g, y - (b // a) * x, x

def mod_inverse(e, phi):
    g, x, _ = extended_euclidean(e, phi)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % phi

e = 13
phi = 1362240

d = mod_inverse(e, phi)
print(d)