#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char b[100010],a1[100010];
int a,c,p=1,nr=-1;
bool bitzi[1000000];
void citire()
{
    scanf("%s\n",a1);
    scanf("%s",b);
    scanf("%d",&c);
    for(int i=1;i<=c;i++)
        p*=10;
     int l=1;
    for(int i=0;i<strlen(a1);i++)
        a=(a*10+(a1[i]-'0'));
    if(strlen(a1)>c)
        a=a%p;
    for(int i=strlen(b)-1;i>=0;i--)
        {
            int n;
            if(b[i]>'9')
           n=((b[i]-'A')+10);
           else
            n=(b[i]-'0');
        for(int j=3;j>=0;j--)
            bitzi[++nr]=n&(1<<j);
        }
}
void facere()
{
    long long rez=0,ap=a,s=a;
    for(int i=nr;i>=0;i--)
    {
        if(bitzi[i])
        {
            rez=(rez*ap+s)%p;
        }
        s=s*(ap+1);
        s=s%p;
        ap=(ap*ap)%p;
    }
    printf("%lld\n",rez);
}
int main()
{
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);
    citire();
    facere();
  //  cout << "Hello world!" << endl;
    return 0;
}