#include <bits/stdc++.h>

using namespace std;

ifstream f("calcul.in");
ofstream g("calcul.out");

int c;
long long MOD=1,x;
string a,b;
bitset <4*50005> bits;

int main()
{
    f>>a>>b>>c;

    for(int i=1; i<=c; i++) MOD=MOD*10;

    int n=a.size();

    for(int i=max(0,n-c); i<n; i++)
        x=x*10+a[i]-'0';

    int nr=0;

    for(int i=0; i<b.size(); i++)
    {
        int number;
        if(b[i]>='0'&&b[i]<='9') number=b[i]-'0';
        else if(b[i]>='A'&&b[i]<='F')number=b[i]-'A'+10;

        for(int j=3; j>=0; j--)
        {
            bits[++nr]=((1<<j)&number);
        }
    }

    long long sol=0,putere=1;

    for(int i=1; i<=nr; i++)
    {
        sol=sol*(1+putere)%MOD;
        putere=putere*putere%MOD;

        if(bits[i]==1)
        {
            putere=putere*x%MOD;
            sol+=putere;
            if(sol>=MOD) sol-=MOD;
        }
    }
    MOD/=10;
    while(sol<MOD)
    {
        g<<'0';
        MOD/=10;
    }
    if(MOD)
        g<<sol;

    return 0;
}