#include<iostream>
#include<string>

using namespace std;

#define NM 200005
#define LL long long

int MOD=1,dim=0; 

char lap[2*NM];
char SA[NM],SB[NM],SC[2];

void sapa(int A,int unde,int &jum,int &sum)
{
     if(unde==dim)
     {
          jum=A;
          sum=A;
          return ;        
     }
     
     sapa(A,unde+1,jum,sum);
     
     int nsum=((LL)sum*(LL)(jum+1))%MOD;
     
     int njum=((LL)jum*jum)%MOD;
     
     if(lap[unde]) 
     {
        nsum=((LL)nsum+(LL)njum*(LL)A)%MOD;
        njum=((LL)njum*A)%MOD;
     }   
     
     sum=nsum,jum=njum;
}

int main()
{   
    int A=0,C,jum,sum;
    
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);
    
    scanf("%s\n%s\n%s",&SA,&SB,&SC);
    
    C=SC[0]-'0';
    
    for(int i=1;i<=C;++i)
       MOD*=10;
    
    int da=strlen(SA);
    
    for(int i=0;i<da;++i)
       A=((LL)A*10+SA[i]-'0')%MOD;
    
    if(A==0)
    {
         printf("0");   
         return 0;
    }
    
    int db=strlen(SB),nr;
    
    for(int i=db-1;i>=0;--i)
    {
        if(SB[i]>='A' && SB[i]<='Z') nr=SB[i]-'A'+10;
        else nr=SB[i]-'0'; 
        
        if(nr&1) lap[dim+1]=1;
        if(nr&2) lap[dim+2]=1;
        if(nr&4) lap[dim+3]=1;
        if(nr&8) lap[dim+4]=1;
        
        dim+=4;     
    }   
    
    while(dim>1 && !lap[dim]) --dim;
    
    /*
    for(int i=1;i<=dim;++i)
      printf("%d",lap[i]);  
    
    printf("\n%d\n%d",A,C);        
    */
    
    sapa(A,1,jum,sum);
    
    nr=sum;
    int catec=0;
    
    if(!nr) ++catec;
    
    while(nr)
    {
        ++catec;
        nr/=10;     
    }
    
    for(int i=1;i<=C-catec;++i)
       printf("0");
    
    printf("%d",sum);
    
    return 0;
}