#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("calcul.in");
ofstream fout("calcul.out");
int i,j,n,m,x,y,c,nr;
char C,sir[100001];
long long rez,aux,prod;
int main()
{
    fin.get(sir,100001);fin.get();
    fin>>C;
    if(C>='1'&&C<='9')
        c=int(C)-48;
    else
        c=int(C)-55;
    fin>>nr;
    n=int(sir[strlen(sir)-i-nr]);
    for(i=sir[strlen(sir)-nr];i<strlen(sir);++i)
        n=n*10+int(sir[i])-48;
    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;
}