#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;
}
if(nr == 0)
nrCif = 1;
while(c-nrCif > 0)
{
nrCif++;
g<<0;
}
g<<nr;
}
int main() {
read();
if(a == 0)
{
print(0);
return 0;
}
matrix start = {{{1, 0}, {a, a}}};
matrix rez = logPower(start, b);
print(rez.a[1][0]);
return 0;
}