#include <fstream>
#include <string.h>
using namespace std;

ifstream fin ("calcul.in");
ofstream fout("calcul.out");

int n,i,j,C,x,a[200010],b[200010],aux;
long long sol,k,MOD=1;
char c[200010];

int main(){
    fin>>(c+1);
    n=strlen(c+1);
    for (i=1;i<=n;i++)
        a[i]=c[i]-'0';
    a[0]=n;
    fin>>(c+1);
    n=strlen(c+1);
    for (i=1;i<=n;i++){
        if (c[i]>='0' && c[i]<='9')
            aux=c[i]-'0';
        else
            aux=c[i]-'A'+10;
        for (j=3;j>=0;j--)
            b[++b[0]]=(aux>>j)%2;
    }
    fin>>C;
    for (i=1;i<=C;i++)
        MOD*=10;
    for (i=max(a[0]-C+1,1);i<=a[0];i++)
        k=k*10+a[i];
    x=1;
    for (i=1;i<=b[0];i++){
        sol=(1LL*sol*(x+1))%MOD;
        x=(1LL*x*x)%MOD;
        if (b[i]){
            sol=(1LL*sol*k+k)%MOD;
            x=(1LL*x*k)%MOD;
        }
    }
    for (MOD/=10;MOD!=1 && sol<MOD;MOD/=10)
        fout<<0;
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}