#include <fstream>
#include <string>
#include <iostream>

using namespace std;

const int MAX_10 = 100000 + 1;
const int MAX_16 =  50000 + 1;

long long s;

long long a;
int c;

int d[MAX_16];
int n;

long long A;

int main() {
    ifstream in("calcul.in");
    string na, nb;
    in >> na >> nb;
    in >> c;

    int st = na.size() - 1 - c;

    int aux = c;
    c = 1;
    for(int i = aux ; i >= 1 ; --i)
        c *= 10;

    if(st < 0)
        st = 0;

    for(int i = st ; i < na.size() ; ++i){
        a = a * 10 + na[i] - '0';
    }
    A = a;

    n = nb.size();
    for(int i = 0 ; i < n ; ++i) {
        if('0' <= nb[i] && nb[i] <= '9')
            d[n - i] = nb[i] - '0';
        else
            d[n - i] = nb[i] - 'A' + 10;
    }

    while(n > 1 && d[n] == 0)
        --n;

    int j;
    for(j = 8 ; j >= 1 && !(d[n] & j) ; j /= 2);

    s = a;
    j /= 2;

    while(j >= 1) {
        s = s * (1 + a) % c;
        a = a * a % c;
        if(d[n] & j) {
            a = a * A % c;
            s = (s + a) % c;
        }
        j /= 2;
    }


    for(int i = n - 1 ; i >= 1 ; --i) {
        for(j = 8 ; j >= 1 ; j /= 2) {
            s = s * (1 + a) % c;
            a = a * a % c;

            if(d[i] & j) {
                a = a * A % c;
                s = (s + a) % c;
            }
        }
    }
    ofstream out("calcul.out");
    out << s << "\n";
    cout << s << "\n";
    return 0;
}