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

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

struct matrix
{
    long long a[2][2];
    void resetMatrix()
    {
        a[0][0] = 0;
        a[0][1] = 0;
        a[1][0] = 0;
        a[1][1] = 0;
    }
};

unordered_map<char, int> base16ToInt = {
        {'0', 0},
        {'1', 1},
        {'2', 2},
        {'3', 3},
        {'4', 4},
        {'5', 5},
        {'6', 6},
        {'7', 7},
        {'8', 8},
        {'9', 9},
        {'A', 10},
        {'B', 11},
        {'C', 12},
        {'D', 13},
        {'E', 14},
        {'F', 15}
};

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

matrix multiply(matrix x, matrix y)
{
    matrix rez;
    rez.resetMatrix();
    for(int i = 0; i<2; ++i)
    {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                rez.a[i][j] = (rez.a[i][j] + (x.a[i][k] * y.a[k][j])%MOD)%MOD;
            }
        }
    }
    return rez;
}

matrix logPower(matrix yes, string s)
{
    matrix rez = {{{1, 0}, {0, 1}}};
    for (int i = b.size()-1; i >= 0; --i) {
        int nr = base16ToInt[b[i]];
        if(i != 0)
        for (int j = 0; j < 4; ++j) {
            if((nr&1) == 1)
                rez = multiply(rez, yes);
            yes = multiply(yes, yes);
            nr>>=1;
        }
        else
        {
            while(nr)
            {
                if((nr&1) == 1)
                    rez = multiply(rez, yes);
                yes = multiply(yes, yes);
                nr>>=1;
            }
        }
    }
    return rez;
}

void read()
{
    string s;
    f>>s>>b>>c;
    for (int i = 0; i < c; ++i) {
        MOD*=10;
    }
    for(int i = max((int)(s.size()-c), 0); i<s.size(); ++i)
        a = a*10+(s[i]-'0');
}

void print(int nr)
{
    int nrCif = 0;
    int aux = nr;
    while(aux)
    {
        nrCif++;
        aux/=10;
    }
    while(c-nrCif > 0)
    {
        nrCif++;
        g<<0;
    }
    g<<nr;
}

int main() {
    read();
    matrix start = {{{1, 0}, {a, a}}};
    matrix rez = logPower(start, b);
    print(rez.a[1][0]);
    return 0;
}