#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long
#include <bits/stdc++.h>


using namespace std;

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

ll A, MOD = 1, a;
ll C;
char B[50005];
ll b[50005];
ll binCounter = 0;

void citire()
{
    in >> A;
    in >> B;
    in >> C;
}

void TakeMod(int x)
{
    for(int i = 1; i <= C; i++)
        MOD *= 10;
}

void TakeA()
{
    a = A % MOD;
}

void TakeB(char x[50005])
{
    int len = strlen(x);

    for(int i = 0; i < len; i++)
    {
        int hex;

        if(x[i] >= '0' && x[i] <= '9')
            hex = x[i] - '0';
        else
            hex = x[i] - 'A' + 10;

        for(int i = 3; i >= 0; i--)
        {
            if(hex & (1 << i))
            {
                b[binCounter++] = 1;
            }

            else
            {
                b[binCounter++] = 0;
            }
        }
    }
}

ll rez()
{
    ll result = 0;
    ll x = 1;

    for (int i = 0; i < binCounter; i++)
    {
        result = (result * (x + 1)) % MOD;
        x = (x * x) % MOD;

        if(b[i])
        {
            x = (x * a) % MOD;
            result = (result + x) % MOD;
        }
    }
    return result;
}

int main()
{
    citire();
    TakeMod(C);
    TakeA();
    TakeB(B);
    out << setfill('0') << setw(C) << rez();
    return 0;
}