#include <fstream>
using namespace std;
ifstream fin ("calcul.in");
ofstream fout ("calcul.out");
char sa[100005],sb[50005];
int c;
int get_nr (char ch)
{
    if (ch>='0'&&ch<='9')
        return ch-'0';
    return ch-'A'+10;
}
int cif (int n)
{
    if (n==0)
        return 1;
    int nr=0;
    while (n>0)
    {
        nr++;
        n/=10;
    }
    return nr;
}
int main ()
{
    fin>>sa>>sb>>c;
    int p=1,a=0;
    for (int i=1; i<=c; i++)
        p=1ll*p*10;
    for (int i=0; sa[i]; i++)
        a=(1ll*a*10+sa[i]-'0')%p;
    int sol=0,nr=1;
    for (int i=0; sb[i]; i++)
    {
        int nrc=get_nr (sb[i]);
        for (int j=3; j>=0; j--)
        {
            int bit=((nrc>>j)&1);
            sol=1ll*sol*(nr+1)%p;
            nr=1ll*nr*nr%p;
            if (bit)
            {
                nr=1ll*nr*a%p;
                sol=(sol+nr)%p;
            }
        }
    }
    int nrc=cif (sol);
    for (int i=1; i<=c-nrc; i++)
        fout<<0;
    fout<<sol;
    return 0;
}