#include<bits/stdc++.h>
using namespace std;

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

int C, A, size_A, size_B, N, Mod, ans, S, val;
int B[200005];
char arr_A[100005], arr_B[50005];

inline void undo_bit( int x ){
    for( int i = 3; i >= 0; i-- )
        B[N++] = (x>>i) & 1;
}

int main(){

    fin.getline( arr_A, 100003 ); size_A = strlen( arr_A );
    fin.getline( arr_B, 50003 ); size_B = strlen( arr_B );
    fin >> C;
    Mod = 1;
    for( int i = 1; i <= C; i++ )
        Mod *= 10;

    for( int i = max( size_A - C, 0 ); i < size_A; i++ )
        A = A * 10 + ( arr_A[i] - '0' );

    for( int i = 0; i < size_B; i++ ){
        if( '0' <= arr_B[i] && arr_B[i] <= '9' )
            undo_bit( arr_B[i]- '0' );
        else
            undo_bit( 10 + arr_B[i] - 'A' );
    }

    int pos = 0;
    while( B[pos] == 0 )
        pos++;

    S = 0, val = 1;
    for( int i = pos; i < N; i++ ){
        if( B[i] == 0 ){
            S = 1LL * S * (1 + val) % Mod;
            val = (1LL * val * val) % Mod;
        }else{
            S = 1LL * S * (1 + val) % Mod;
            val = (val * val) % Mod;
            S = (1LL * S * A + A) % Mod;
            val = (1LL * val * A) % Mod;
        }
    }

    S %= Mod;
    int p = Mod / 10;
    while( p != 1 ){
        if( S < p )
            fout << 0;
        p /= 10;
    }
    fout << S;
    return 0;
}