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

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

const int DIM = 200010;

string str1, str2; bool aux[DIM];

int main( void ) {
    ios::sync_with_stdio( false );
    
    int a = 0, c, mod = 1;
    in >> str1 >> str2 >> c;
    
    for( int i = max( 0, (int) str1.length() - c ); i <= str1.length() - 1; i ++ )
        a = a * 10 + ( str1[i] - '0' );
    
    int n = 0;
    for( int i = str2.length() - 1; i >= 0; i -- ) {
        int x = ( ( str2[i] >= 'A' && str2[i] <= 'Z' ) ? ( str2[i] - 'A' + 10 ) : ( str2[i] - '0' ) );
        
        for( int j = 0; j <= 3; j ++ )
            aux[++ n] = ( (x >> j) & 1 );
    }
    
    for( int i = 1; i <= c; i ++ )
        mod = mod * 10;
    
    int ans = 0, aux1 = a, aux2 = a;
    for( int i = 1; i <= n; i ++ ) {
        if( aux[i] == true )
            ans = ( ans * 1LL * aux1 + aux2 ) % mod;
        
        aux2 = ( aux2 * 1LL * aux1 + aux2 ) % mod;
        aux1 = ( aux1 * 1LL * aux1 ) % mod;
    }
    
    int cnt = to_string( ans ).length();
    for( int i = 1; i <= c - cnt; i ++ )
        out << "0";
    out << ans << endl;
    
    return 0;
}