RSA common module attack

ex.py

#!/usr/lib/env python
#-*-coding: utf-8-*-
#author:Racter

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)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

p = int(240670121804208978394996710730839069728700956824706945984819015371493837551238)
q = int(63385828825643452682833619835670889340533854879683013984056508942989973395315)
M = int(349579051431173103963525574908108980776346966102045838681986112083541754544269)
z = int(213932962252915797768584248464896200082707350140827098890648372492180142394587)
m = int(282832747915637398142431587525135167098126503327259369230840635687863475396299)
x = int(254732859357467931957861825273244795556693016657393159194417526480484204095858)
y = int(261877836792399836452074575192123520294695871579540257591169122727176542734080)

b = int(-1037053409024003793188915820925495612693130512199951020513082330855499409786432)
a = int(-310932636473806864327001349777025538639559989997125579267263744895242746696733)
c = int(-621317938970814523386160249592941721897243644392471590115387137591562627584532488)

s = egcd(a, b)
s1 = s[1]
s2 = s[2]
print s
n=M
if s1<0:
    s1 = - s1
    p = modinv(p, n)
elif s2<0:
    s2 = - s2
    q = modinv(q, n)
flag=(pow(p,s1,n)*pow(q,s2,n)) % n
print flag

abc