def egcd(a,b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def gcd(a,b):
a,b=(b,a) if a<b else (a,b)
while b:
a,b=b,a%b
return a
def modInverse(e,n):#will help me find the private key!
return egcd(e,n)[0]%n
def totient(p,q):
return (p-1)*(q-1)
#e=int(raw_input())
#ct=1520
#n=int(raw_input())
def encode(ct,n,e):
ans=(ct**modInverse(e,n))%n
return ans
def decode(n,e):
ans=(encode(ct,n,e)**modInverse(e,n))%n
return ans
e = 2667263
n = 118161264594682552213478835740008518638148382236836652791249450378665869820660982155245457006168819364532380817733
ct=4972012305304213038212726495362
#d=modInverse(e,n)
#print encode(ct,n,e)
#print decode(n,e)
print decode(n,e)
Please help me solve this problem, when I run this program with small integers it does run, but for the one given above it doesn't. it's RSA Cryptography related