#include <iostream>
#include <fstream>
#include <cstring>

#define ll long long

using namespace std;

ll a, b, c, mod = 1;
char B;

void Calc_Mod()
{
    for(ll i=1; i<=c; ++i)
        mod *= 10;
}

void Calc_B()
{
    if(isdigit(B))
        b=B-'0';
    else
        b=B-'A'+10;
}

ll Rid_Exp(ll nr, ll po)
{
    ll rez = 1;

    do
    {
     if(po & 1)
        rez = (nr*rez)%mod;

     nr=(nr*nr)%mod;
     po = po >> 1;
    }while(po);

    return rez;
}

pair < ll, ll > euclid_extins(ll x, ll y)
{
    if(y==0)
    {
        return {1,0};
    }

    pair < ll, ll > aux = euclid_extins(y,x%y);
    ll rap = x/y;
    return {aux.second, aux.first - rap * aux.second};
}

int main()
{
    ifstream fin("calcul.in");
    ofstream fout("calcul.out");
    fin>>a;
    fin>>B;
    fin>>c;

    Calc_Mod();
    Calc_B();
    ll rez = 1LL * (Rid_Exp(a,b+1) - 1);
    ll rap = 1LL * euclid_extins(a-1,mod).first;
    fout << ((1LL * (rez%mod) * (1LL * rap%mod)%mod-1)%mod);
    return 0;
}