from Crypto.Util.number import long_to_bytes
def decrypt(c=0, d=0, n=0):
    s = 0;
    s = pow(c, d, n)
    return 37991937053350834320678619330546903567320901767090609881924528835279022654346
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m
 
 
p = 857504083339712752489993810777
n = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
q = 1029224947942998075080348647219
r = (p - 1) * (q - 1)
d = modinv(e, r)
m = 4805456
#print long_to_bytes(m)
c = pow(m, e, n)
print long_to_bytes(decrypt(c, d, n))
print (d)

ZnJvbSBDcnlwdG8uVXRpbC5udW1iZXIgaW1wb3J0IGxvbmdfdG9fYnl0ZXMKZGVmIGRlY3J5cHQoYz0wLCBkPTAsIG49MCk6CiAgICBzID0gMDsKICAgIHMgPSBwb3coYywgZCwgbikKICAgIHJldHVybiAzNzk5MTkzNzA1MzM1MDgzNDMyMDY3ODYxOTMzMDU0NjkwMzU2NzMyMDkwMTc2NzA5MDYwOTg4MTkyNDUyODgzNTI3OTAyMjY1NDM0NgoKZGVmIGVnY2QoYSwgYik6CiAgICBpZiBhID09IDA6CiAgICAgICAgcmV0dXJuIChiLCAwLCAxKQogICAgZWxzZToKICAgICAgICBnLCB5LCB4ID0gZWdjZChiICUgYSwgYSkKICAgICAgICByZXR1cm4gKGcsIHggLSAoYiAvLyBhKSAqIHksIHkpCgoKZGVmIG1vZGludihhLCBtKToKICAgIGcsIHgsIHkgPSBlZ2NkKGEsIG0pCiAgICByZXR1cm4geCAlIG0KCgpwID0gODU3NTA0MDgzMzM5NzEyNzUyNDg5OTkzODEwNzc3Cm4gPSA4ODI1NjQ1OTU1MzYyMjQxNDA2Mzk2MjU5ODc2NTk0MTYwMjk0MjYyMzkyMzA4MDQ2MTQ2MTMyNzkxNjMKZSA9IDY1NTM3CmMgPSA3NzU3ODk5NTgwMTE1NzgyMzY3MTYzNjI5ODg0NzE4NjcyMzU5MzgxNDg0Mzg0NTUyNTIyMzMwMzkzMgpxID0gMTAyOTIyNDk0Nzk0Mjk5ODA3NTA4MDM0ODY0NzIxOQpyID0gKHAgLSAxKSAqIChxIC0gMSkKZCA9IG1vZGludihlLCByKQptID0gNDgwNTQ1NgojcHJpbnQgbG9uZ190b19ieXRlcyhtKQpjID0gcG93KG0sIGUsIG4pCnByaW50IGxvbmdfdG9fYnl0ZXMoZGVjcnlwdChjLCBkLCBuKSkKcHJpbnQgKGQp