p = 201522792635114097998567775554303915819
q = 236811285547763449711675622888914229291 
e = 65537
n = (p-1)*(q-1)

def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a // b) * y)
        #print(x,y,q)
        return x, y, q


def test_egcd():
    ret = ext_euclid(e, n)
    d = ret[0]
    if d < 0:
        d = d + (p-1)*(q-1)
    print(d)

if __name__ == '__main__':
    test_egcd()