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

ifstream in("calcul.in");
ofstream out("calcul.out");
string astr,bstr;

int a, b, c;
int MOD = 1;

inline int get_dec(char c)
{
    if(c>='0' && c<='9')
        return c-'0';
    if(c>='A' && c<='F')
        return 10 + c - 'A';
}

int power(int x,int p)
{
    if(p==1) return x;

    if((p&1)==0)
    {
        int y = power(x,p/2) % MOD;
        return (y*y) % MOD;
    }
    return (x*power(x,p-1))%MOD;
}

void cmmdc(int a,int b,int &d,int &k, int &l)
{
    if(b==0)
    {
        d=a;
        k = 1;
        l = 0;
    }
    else
    {
        int k0, l0;
        cmmdc(b,a%b,d,k0,l0);

        k = l0;
        l = k0 - (a/b)*l0;
    }
}


int main()
{
    ios::sync_with_stdio(false);

    in>>astr>>bstr>>c;

    for(int i=1;i<=c;i++)
        MOD *= 10;

    for(int i=astr.size()-1;i>=0;i--)
        a = a * 10 + astr[i]-'0';

    for(int i=bstr.size()-1;i>=0;i--)
        b = b * 16 + get_dec(bstr[i]);

    int numarator = power(a,b+1) - a;

    int x, y, d;
    cmmdc(a-1,MOD,d,x,y);

    while(x<0) x+= MOD;

    out<<numarator * x;

    return 0;
}