#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int nmax=200111;
int n ,c ,bit[nmax], MOD=1;
char str[nmax], str2[nmax];
long long a, sol[2][2], t[2][2];
int main()
{
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);
    scanf("%s %s %d", &str, &str2, &c);
    for( int i=1;i<=c;++i) MOD*=10;
    for(int i=0; i<strlen(str); ++i)
    {
        a*=10;
        a+=str[i]-'0';
        a%=MOD;
    }
    int ind=0;
    for(int i=strlen(str2)-1; i>=0; --i)
    {
        int val=str2[i]-'0';
        if('A'<=str2[i] && str2[i]<='Z')val=10+str2[i]-'A';
        for(int k=0; k<4; ++k)
        {
            bit[++ind]=val%2;
            val/=2;
        }
    }
    sol[0][0]=1; sol[0][1]=0;
    sol[1][0]=0; sol[1][1]=1;
    t[0][0]=a; t[0][1]=a;
    t[1][0]=0; t[1][1]=1;
    for(int x=1; x<=ind; x++)
    {
        if(bit[x])
        {
            long long aux[2][2];
            for( int i=0; i<2; ++i)
                for(int j=0; j<2; ++j)
                {
                    aux[i][j]=0;
                    for(int k=0; k<2; ++k)
                    {
                        aux[i][j]+=sol[i][k]*t[k][j];
                        aux[i][j]%=MOD;
                    }
                }
            for( int i=0; i<2; ++i)
                for( int j=0;j<2;++j)
                    sol[i][j]=aux[i][j];
        }
        long long aux[2][2];
        for(int i=0; i<2; ++i)
            for( int j=0; j<2; ++j)
            {
                aux[i][j]=0;
                for(int k=0; k<2; ++k)
                {
                    aux[i][j]+=t[i][k]*t[k][j];
                    aux[i][j]%=MOD;
                }
            }

        for( int i=0;i<2;++i)
            for( int j=0;j<2;++j)
                t[i][j]=aux[i][j];
    }

    long long x=sol[0][1];
    while(x<(MOD/10))
    {
        MOD/=10;
        cout<<"0";
    }
    if(sol[0][1])
        cout<<sol[0][1];
    fclose(stdin);
    fclose(stdout);
    return 0;
}