#include <fstream>
#include <cstring>
using namespace std;

char nr_a[100005], nr_b[50005];

short b[200005], a[11], power_a[200005][11], sumpow[200005][11], res[11], temp[11];

void transf_a(){
    int lung=strlen(nr_a);
    for(int i=1; i<=9&&i<=lung; ++i){
        a[i]=(int)nr_a[lung-i]-48;
    }
}

void transf_b(){
    int lung=strlen(nr_b), power=0, val, rest;
    for(int i=lung-1; i>=0; --i){
        if(nr_b[i]>='0'&&nr_b[i]<='9'){
            val=(int)(nr_b[i]-'0');
        }
        else val=(int)(nr_b[i]-'A')+10;
        while(val>0){
            rest=val%2;
            if(rest){
                b[power+4*(lung-1-i)]++;
            }
            power++;
            val/=2;
        }
        power=0;
    }
}

void copiere(short v1[11], short v2[11]){
    for(int i=1; i<=9; ++i){
        v1[i]=v2[i];
    }
}

void suma(short v1[11], short v2[11], short v3[11]){
    int rest=0;
    for(int i=1; i<=9; ++i){
        v3[i]=(v1[i]+v2[i]+rest)%10;
        rest=(rest+v1[i]+v2[i])/10;
    }
}

void inmultire(short v1[11], short v2[11], short v3[11]){
    for(int i=1; i<=9; ++i)
        v3[i]=0;
    int rest=0;
    for(int i=1; i<=9; ++i){
        for(int j=1; j<=9; ++j){
            if(i+j-1<=9){
                v3[i+j-1]+=(v1[j]*v2[i]+rest)%10;
                rest=(v1[j]*v2[i]+rest)/10;
            }
        }
        rest=0;
    }
    for(int i=1; i<=9; ++i){
        if(v3[i]/10){
            v3[i+1]+=(v3[i]/10);
            v3[i]%=10;
        }
    }
}

void puteri(){
    copiere(power_a[0], a);
    copiere(sumpow[0], a);
    for(int i=1; i<=200001; ++i){
        inmultire(power_a[i-1], power_a[i-1], power_a[i]);
        inmultire(sumpow[i-1], power_a[i-1], temp);
        suma(sumpow[i-1], temp, sumpow[i]);
    }
}

void solve(int power){
    if(power==0){
        if(b[power])copiere(res, power_a[0]);
        goto pas;
    }
    if(b[power]==0)
        solve(power-1);
    else {
        solve(power-1);
        inmultire(res, power_a[power], temp);
        copiere(res, temp);
        suma(res, sumpow[power], temp);
        copiere(res, temp);
    }
    pas: ;
}

int main()
{
    ifstream in("calcul.in");
    ofstream out("calcul.out");
    in.get(nr_a, 100001);
    in.get();
    in.get(nr_b, 50005);
    int c;
    in>>c;
    transf_a();
    transf_b();
    puteri();
    solve(200001);
    for(int i=c; i>=1; --i){
        out<<res[i];
    }
    out<<"\n";
    in.close();
    out.close();
    return 0;
}