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()