// BOJ 4862 - 마지막 자리
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll modpow(ll a, ll b, ll c) {
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % c;
b >>= 1;
a = a * a % c;
}
return ret;
}
ll phi(ll n) {
ll result = n;
for (ll i = 2; i * i <= n; ++i) {
if (n % i == 0) {
result -= result / i;
while (n % i == 0) n /= i;
}
}
if (n > 1)
result -= result / n;
return result;
}
ll naive(const ll b, const ll x, const ll m) {
if (x == 0) return 1;
else return modpow(b, naive(b, x - 1, m), m);
}
ll f(const ll b, const ll x, const ll m) {
if (m == 1) return 1; // 대신 마지막에 f(b, x, m) % m을 해줘야 함
if (x == 0) return 1;
if (x <= 5) return naive(b, x, m);
// a^p = a^(p mod phi(m) + phi(m)) mod m을 이용해 구할 수 있다.
const ll p = phi(m);
return modpow(b, f(b, x - 1, p) + p, m);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while (true) {
int b, i, n;
cin >> b;
if (b == 0) break;
cin >> i >> n;
ll m = 1;
for (int j = 0; j < n; j++) {
m *= 10;
}
cout << setw(n) << setfill('0') << f(b, i, m) % m << endl;
}
return 0;
}
Ly8gQk9KIDQ4NjIgLSDrp4jsp4Drp4kg7J6Q66asCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGVuZGwgIlxuIgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbGwgPSBsb25nIGxvbmc7CnVzaW5nIHVsbCA9IHVuc2lnbmVkIGxvbmcgbG9uZzsKCmxsIG1vZHBvdyhsbCBhLCBsbCBiLCBsbCBjKSB7CiAgICBsbCByZXQgPSAxOwogICAgd2hpbGUgKGIpIHsKICAgICAgICBpZiAoYiAmIDEpIHJldCA9IHJldCAqIGEgJSBjOwogICAgICAgIGIgPj49IDE7CiAgICAgICAgYSA9IGEgKiBhICUgYzsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCmxsIHBoaShsbCBuKSB7CiAgICBsbCByZXN1bHQgPSBuOwoKICAgIGZvciAobGwgaSA9IDI7IGkgKiBpIDw9IG47ICsraSkgewogICAgICAgIGlmIChuICUgaSA9PSAwKSB7CiAgICAgICAgICAgIHJlc3VsdCAtPSByZXN1bHQgLyBpOwogICAgICAgICAgICB3aGlsZSAobiAlIGkgPT0gMCkgbiAvPSBpOwogICAgICAgIH0KICAgIH0KCiAgICBpZiAobiA+IDEpCiAgICAgICAgcmVzdWx0IC09IHJlc3VsdCAvIG47CgogICAgcmV0dXJuIHJlc3VsdDsKfQoKbGwgbmFpdmUoY29uc3QgbGwgYiwgY29uc3QgbGwgeCwgY29uc3QgbGwgbSkgewogICAgaWYgKHggPT0gMCkgcmV0dXJuIDE7CiAgICBlbHNlIHJldHVybiBtb2Rwb3coYiwgbmFpdmUoYiwgeCAtIDEsIG0pLCBtKTsKfQoKbGwgZihjb25zdCBsbCBiLCBjb25zdCBsbCB4LCBjb25zdCBsbCBtKSB7CiAgICBpZiAobSA9PSAxKSByZXR1cm4gMTsgLy8g64yA7IugIOuniOyngOunieyXkCBmKGIsIHgsIG0pICUgbeydhCDtlbTspJjslbwg7ZWoCiAgICBpZiAoeCA9PSAwKSByZXR1cm4gMTsKICAgIGlmICh4IDw9IDUpIHJldHVybiBuYWl2ZShiLCB4LCBtKTsKCiAgICAvLyBhXnAgPSBhXihwIG1vZCBwaGkobSkgKyBwaGkobSkpIG1vZCBt7J2EIOydtOyaqe2VtCDqtaztlaAg7IiYIOyeiOuLpC4KICAgIGNvbnN0IGxsIHAgPSBwaGkobSk7CiAgICByZXR1cm4gbW9kcG93KGIsIGYoYiwgeCAtIDEsIHApICsgcCwgbSk7Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwogICAgY291dC50aWUobnVsbHB0cik7CgogICAgd2hpbGUgKHRydWUpIHsKICAgICAgICBpbnQgYiwgaSwgbjsKICAgICAgICBjaW4gPj4gYjsKICAgICAgICBpZiAoYiA9PSAwKSBicmVhazsKICAgICAgICBjaW4gPj4gaSA+PiBuOwoKICAgICAgICBsbCBtID0gMTsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG47IGorKykgewogICAgICAgICAgICBtICo9IDEwOwogICAgICAgIH0KCiAgICAgICAgY291dCA8PCBzZXR3KG4pIDw8IHNldGZpbGwoJzAnKSA8PCBmKGIsIGksIG0pICUgbSA8PCBlbmRsOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==