#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("calcul.in");
ofstream fout("calcul.out");
int i,j,n,m,x,y,c,nr;
char C;
long long rez,aux,prod;
int main()
{
    fin>>n;
    fin>>C;
    if(C>='1'&&C<='9')
        c=int(C)-48;
    else
        c=int(C)-55;
    fin>>nr;
    aux=1;
    for(i=1;i<=nr;++i)
        aux*=10;
    n=n%aux;
    rez=n;
    prod=n;
    for(i=2;i<=c;++i)
        {
            prod=prod*n;
            prod=prod%aux;
            rez+=prod;
            rez=rez%aux;
        }
    fout<<rez<<'\n';
    return 0;
}