#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("calcul.in");
ofstream fout("calcul.out");
char anr[100005],b[100005];
int c,MOD=1,l,lb,a,mat[2][2],rez[2][2];
void modul()
{
    for(int i=1;i<=c;i++)
        MOD*=10;
}
void calcA()
{   int p=0;
    if(l>c)
        p=l-c;
    
    for(int i=p;i<l;i++)
    {
        a=a*10+(anr[i]-'0');
    }
}
void form()
{
    mat[0][0]=1;
    mat[1][0]=a;
    mat[1][1]=a;
}
void ridicare(int m1[2][2],int m2[2][2],int m3[2][2] )
{   int temp[2][2]={(0,0),(0,0)};
    for(int i=0;i<2;i++)
        for (int j=0; j<2; j++)
            for(int k=0;k<2;k++)
                temp[i][j]=(temp[i][j]+ (1LL*m1[i][k] * m2[k][j])%MOD )%MOD;
    
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            m3[i][j]=temp[i][j];
        
}
int hex(char x)
{
    if(x>='0' && x<='9')
        return x-'0';
    return x-'A'+10;
}
 void rise(int m[2][2],int rez[2][2])
{
    rez[0][0]=rez[1][1]=1;
    rez[0][1]=rez[1][0]=0;
    for(int i=lb-1;i>=0;i--)
    {
    int cif=hex(b[i]);
    for(int ind=0;ind<4;ind++)
    {
         
        int bit=(cif>>ind)&1;
        if(bit==1)
            ridicare(rez, m, rez);
        ridicare(m, m, m);
        
    }
        
    }
    
}
int numar(int x)
{
    int nr=0;
    do{
        nr++;
        x/=10;
    }while (x);
    return nr;
}
void afisare()
{
    int nr=numar(rez[1][0]);
    for(int i=1;i<=c-nr;i++)
        fout<<"0";
    fout<<rez[1][0];
}
int main() {
    fin>>a;
    l=strlen(anr);
    if(anr[l-1]=='\n')
        anr[l--]=0;
    fin>>b;
    lb=strlen(b);
    if(b[l-1]=='\n')
        b[lb--]=0;
    fin>>c;
    modul();
    calcA();
    form();
    rise(mat, rez);
    afisare();
    return 0;
}