#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// `mod` diye yeni bir parametre geldi.
// Sonucun `mod`a bölümünden kalanı döndüreceğiz.
ll bin_exp(ll taban, ll us, ll mod) {
    // İpucu: Uygunsa Fermat'ın küçük teoremini, üssü küçültmek için kullanabilirsiniz.
 
    // ÖNEMLİ: Başta şunu yapıyoruz ki sonradan bir overflow meydana gelmesin.
    // Basit bir modüler aritmetik bilgisini uyguluyoruz.
    taban %= mod;
 
    ll cevap = 1;
 
    while (us) {
        if (us % 2) {
            (cevap *= taban) %= mod;
        }
 
        (taban *= taban) %= mod;
        us /= 2;
    }
 
    return cevap;
}
 
int main() {
    ll taban, us, mod;
    cin >> taban >> us >> mod;
    cout << taban << "^" << us << " mod " << mod << " = " << bin_exp(taban, us, mod) << "\n";
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwoKLy8gYG1vZGAgZGl5ZSB5ZW5pIGJpciBwYXJhbWV0cmUgZ2VsZGkuCi8vIFNvbnVjdW4gYG1vZGBhIGLDtmzDvG3DvG5kZW4ga2FsYW7EsSBkw7ZuZMO8cmVjZcSfaXouCmxsIGJpbl9leHAobGwgdGFiYW4sIGxsIHVzLCBsbCBtb2QpIHsKICAgIC8vIMSwcHVjdTogVXlndW5zYSBGZXJtYXQnxLFuIGvDvMOnw7xrIHRlb3JlbWluaSwgw7xzc8O8IGvDvMOnw7xsdG1layBpw6dpbiBrdWxsYW5hYmlsaXJzaW5pei4KCiAgICAvLyDDlk5FTUzEsDogQmHFn3RhIMWfdW51IHlhcMSxeW9ydXoga2kgc29ucmFkYW4gYmlyIG92ZXJmbG93IG1leWRhbmEgZ2VsbWVzaW4uCiAgICAvLyBCYXNpdCBiaXIgbW9kw7xsZXIgYXJpdG1ldGlrIGJpbGdpc2luaSB1eWd1bHV5b3J1ei4KICAgIHRhYmFuICU9IG1vZDsKCiAgICBsbCBjZXZhcCA9IDE7CgogICAgd2hpbGUgKHVzKSB7CiAgICAgICAgaWYgKHVzICUgMikgewogICAgICAgICAgICAoY2V2YXAgKj0gdGFiYW4pICU9IG1vZDsKICAgICAgICB9CgogICAgICAgICh0YWJhbiAqPSB0YWJhbikgJT0gbW9kOwogICAgICAgIHVzIC89IDI7CiAgICB9CgogICAgcmV0dXJuIGNldmFwOwp9CgppbnQgbWFpbigpIHsKICAgIGxsIHRhYmFuLCB1cywgbW9kOwogICAgY2luID4+IHRhYmFuID4+IHVzID4+IG1vZDsKICAgIGNvdXQgPDwgdGFiYW4gPDwgIl4iIDw8IHVzIDw8ICIgbW9kICIgPDwgbW9kIDw8ICIgPSAiIDw8IGJpbl9leHAodGFiYW4sIHVzLCBtb2QpIDw8ICJcbiI7Cn0=

MTAwMDAwMDAwMDAwMDAwMDAwMCAxMDAwMDAwMDAwMDAwMDAwMDAwIDEwMDAwMDAwMDc=

1000000000000000000 1000000000000000000 1000000007