#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,numar;
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;
    if(strlen(sir)<=nr)
        n=strtol(sir,NULL,10);
    else
        n=strtol(sir+(strlen(sir)-nr),NULL,10);

    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;

        }
    aux=rez;
    while(aux!=0)
    {
        numar++;
        aux=aux/10;
    }
    if(numar<=nr)
        while(numar!=nr)
        {
            fout<<0;
            numar++;
        }
    if(rez==0)
    for(i=1;i<=nr;++i)
    fout<<rez;
    else
    fout<<rez;

    return 0;
}