#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
typedef  __int64 u64;
#define FOR(i,s,e) for( u64  (i)=(s); (i) < (e) ; i++)
u64 gcd(u64 a,u64 b)
{
    if (a < b) return gcd(b,a);
    u64 c;
    while (b) {c=a%b;a=b;b=c;}
    return a;
}
 bool is[130000]; 
int prm[30000];
int totleprm;
int getprm(u64  n)
{
     u64  i, j, k = 0;
    int s, e = (int)(sqrt(0.0 + n) + 1);
    memset(is, 1, sizeof(is));
    prm[k++] = 2;
    is[0] = is[1] = 0;
    for (i = 4; i < n; i +=2) is[i] = 0;
    for (i = 3; i < e; i +=2) if(is[i])
    {    prm[k++] = i;
        for (s = i * 2, j = i * i ; j < n; j +=s)
        is[j] = 0;
        }
    for (; i < n; i +=2)
    if (is[i])     prm[k++] = i;
    return k;
}
//这个题目秒就秒在这个函数
u64 newMod(u64 n, u64 m)
{
    if (n < m) return n;
    else
        return n%m+m;
}
u64  power_mod(u64 A, u64  B, u64 C)
{
     if (B == 0) return 1%C;
    u64  R = 1, D = A;
    while (B )
    {
//注意这里跟以前的不同
        if (B&1) R =newMod(R*D,C);
        D = newMod(D*D,C);
        B >>=1;
    }
    return R;
}

u64  euler(u64  x)
{
    int i ;
    u64  res = x;
    for (i = 0; prm[i] < (u64 )sqrt(x * 1.0) + 1 && i < totleprm; i++)
    if (x % prm[i] == 0)
    {
        res = res / prm[i] *( prm[i] - 1);

        while (x % prm[i] == 0 ) x/=prm[i];
        }
if (x > 1) res = res / x * (x-1);
    return res;
}
  
u64 f(u64 b_v,u64 n, u64 m_v)
{
	  if (m_v == 1) return 0;
	  if (n == 1) return newMod(b_v,m_v);
	  u64 ph=euler(m_v);
	  u64 k = f(b_v,n-1,ph);
	  return power_mod(b_v,k,m_v);
}   
u64 sign[110][110];
int main()
{
     u64 b,n,k;
     u64 m;
     int a[20]    ;
     memset(sign,-1,sizeof(sign));
  //   freopen("in.txt","r",stdin);
     totleprm = getprm(130000);
     while (scanf("%I64d",&b),b>0)
     {
         scanf("%I64d%I64d",&n,&k);
         u64 ans;
         m=10000000;
//必须记录，否则会超时
         if (sign[b][n] < 0)
          sign[b][n]= ans = f(b,n,m);
         else
          ans=sign[b][n];

         FOR(i,0,k)    
             a[i]=0;
         int j = k-1;
         while (ans>0 && j>=0)
         {a[j]=ans%10;ans/=10;j--;}
         FOR(i,0,k)
             printf("%d",a[i]);
         printf("\n");
     }
     return 0;
}