# Written by Tacet
def totient(n) : # n - unsigned int
result = 1
p = 2 #prime numbers - 'iterator'
while p**2 <= n :
if(n%p == 0) : # * (p-1)
result *= (p-1)
n /= p
while(n%p == 0) : # * p^(k-1)
result *= p
n /= p
p += 1
if n != 1 :
result *= (n-1)
return result
def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod m
if m == 2:
return p % m
cp = 0
while m % p == 0 :
cp += 1
m /= p # m = m' now
t = totient(m)
exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t
# exponent = z*(b^c)-cp mod t
return pow(p, cp)*pow(p, exponent, m)
def solve(a,b,c,m) : #split
result = 1
p = 2
while p**2 <= a :
cp = 0
while a%p == 0 :
a /= p
cp += 1
if cp != 0 :
temp = modpow(p,cp,b,c,m)
result *= temp
result %= m
p += 1
if a != 1 :
result *= modpow(a, 1, b, c, m)
return result % m
print solve(5**2 * 97* 7**30 * 2, 9878789, 1214712, 13**2 * 2* 7**8)
# (5^2 * 97* 7^30 * 2)^(9878789^1214712) mod (13**2 * 2* 7**8)
#Silence!
IyBXcml0dGVuIGJ5IFRhY2V0CmRlZiB0b3RpZW50KG4pIDogICAgICAgICAgIyBuIC0gdW5zaWduZWQgaW50CiAgICByZXN1bHQgPSAxCiAgICBwID0gMiAgICAgICAgICAgICAgICAgI3ByaW1lIG51bWJlcnMgLSAnaXRlcmF0b3InCiAgICB3aGlsZSBwKioyIDw9IG4gOgogICAgICAgIGlmKG4lcCA9PSAwKSA6ICAgICMgKiAocC0xKQogICAgICAgICAgICByZXN1bHQgKj0gKHAtMSkKICAgICAgICAgICAgbiAvPSBwCiAgICAgICAgd2hpbGUobiVwID09IDApIDogIyAqIHBeKGstMSkKICAgICAgICAgICAgcmVzdWx0ICo9ICBwCiAgICAgICAgICAgIG4gLz0gcAogICAgICAgIHAgKz0gMQogICAgaWYgbiAhPSAxIDoKICAgICAgICByZXN1bHQgKj0gKG4tMSkKICAgIHJldHVybiByZXN1bHQKCmRlZiBtb2Rwb3cocCwgeiwgYiwgYywgbSkgOiAjIChwXnopXihiXmMpIG1vZCBtCiAgICBpZiBtID09IDI6CiAgICAgICAgcmV0dXJuIHAgJSBtCiAgICBjcCA9IDAKICAgIHdoaWxlIG0gJSBwID09IDAgOgogICAgICAgIGNwICs9IDEKICAgICAgICBtIC89IHAgICAgICAgICAgICAgICMgbSA9IG0nIG5vdwogICAgdCA9IHRvdGllbnQobSkKICAgIGV4cG9uZW50ID0gKChwb3coYixjLHQpKnopJXQgKyB0IC0gKGNwJXQpKSV0CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIGV4cG9uZW50ID0geiooYl5jKS1jcCBtb2QgdAogICAgcmV0dXJuIHBvdyhwLCBjcCkqcG93KHAsIGV4cG9uZW50LCBtKQoKZGVmIHNvbHZlKGEsYixjLG0pIDogI3NwbGl0CiAgICByZXN1bHQgPSAxCiAgICBwID0gMgogICAgd2hpbGUgcCoqMiA8PSBhIDoKICAgICAgICBjcCA9IDAKICAgICAgICB3aGlsZSBhJXAgPT0gMCA6CiAgICAgICAgICAgIGEgLz0gcAogICAgICAgICAgICBjcCArPSAxCiAgICAgICAgaWYgY3AgIT0gMCA6CiAgICAgICAgICAgdGVtcCA9ICBtb2Rwb3cocCxjcCxiLGMsbSkKICAgICAgICAgICByZXN1bHQgKj0gdGVtcAogICAgICAgICAgIHJlc3VsdCAlPSBtCiAgICAgICAgcCArPSAxCiAgICBpZiBhICE9IDEgOgogICAgICAgIHJlc3VsdCAqPSBtb2Rwb3coYSwgMSwgYiwgYywgbSkKICAgIHJldHVybiByZXN1bHQgJSBtCgpwcmludCBzb2x2ZSg1KioyICogOTcqIDcqKjMwICogMiwgOTg3ODc4OSwgMTIxNDcxMiwgMTMqKjIgKiAyKiA3Kio4KQojICg1XjIgKiA5NyogN14zMCAqIDIpXig5ODc4Nzg5XjEyMTQ3MTIpIG1vZCAoMTMqKjIgKiAyKiA3Kio4KQojU2lsZW5jZSE=