RSA given q, p and e? I am given the q, p, and e values for an RSA key, along with an encrypted message.

Here are those values:  

p                 = 1090660992520643446103273789680343  
q                 = 1162435056374824133712043309728653  
e                 = 65537  
sample ciphertext = 299604539773691895576847697095098784338054746292313044353582078965  


I tried calculating d with the Extended Euclidean algorithm, but came out as 1.9404359e+59, which I am almost certain is incorrect. How should I calculate d?
I used the following python code to compute the private exponent and perform decryption. It uses the extended euclidean algorithm:

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def main():

    p = 1090660992520643446103273789680343
    q = 1162435056374824133712043309728653
    e = 65537
    ct = 299604539773691895576847697095098784338054746292313044353582078965

    # compute n
    n = p * q

    # Compute phi(n)
    phi = (p - 1) * (q - 1)

    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()


The private exponent is:

$522550976146069021499058157764354003336248628589338241039193114657$

The plaintext is:

$83678269879577658472958479799572658268$

which works out to a 128-bit value, so I'm assuming it's correct.