#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef unsigned long long ull; using namespace std; typedef long long ll; const int maxn=5e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k,d[205]; struct big { vector<int>v; void ip(){ v.clear(); string s;cin>>s; reverse(s.begin(),s.end()); for(char c:s)v.p_b(isdigit(c)?c-'0':c-'A'+10); } }; big operator*(big a,big b){ big c;c.v.resize(a.v.size()+b.v.size()-1); up(i,0,(int)a.v.size()-1) up(j,0,(int)b.v.size()-1) c.v[i+j]+=a.v[i]*b.v[j]; up(i,0,(int)c.v.size()-2)c.v[i+1]+=c.v[i]>>4,c.v[i]&=15; while(c.v.back()>=16){ c.v.p_b(c.v.back()>>4); c.v[c.v.size()-2]&=15; } //for(int x:c.v)cout<<x<<" ";cout<<endl; return c; } struct _ { ull a,b; void cl(){a=b=0;} }f[105],g[105]; int val[555]; void slv(){ n=read(),k=read(); big a,b;a.ip();up(i,0,k-1)b.v.p_b(15); a=a*b;int m=(n+k-1)/k+1; ull res=0; //cout<<m*16<<endl; up(i,1,m-1){ big c=b*((big){{i}}); memset(val,0,sizeof(val)); int prod=16; up(j,0,(int)c.v.size()-1){ if(j>=k)val[k-1]+=c.v[j]*prod,prod*=16; else val[j]+=c.v[j]; } //cout<<"! "<<val[k-1]<<endl; //up(j,0,k-1)cout<<val[j]<<" ";cout<<endl; //cout<<"test "<<c.v.size()<<" "<<a.v.size()<<endl; up(j,0,(int)a.v.size()-1){ //memset(f,0,sizeof(f)); up(l,0,100)f[l].cl(); f[0].a=1; up(l,0,k-1){ up(p,0,m-1){ int Pos=p*k+l; //cout<<"Pos "<<p<<" "<<a.v[Pos]<<endl; if(Pos>=a.v.size())continue; //cout<<"Pos = "<<Pos<<" "<<a.v[Pos]<<endl; up(q,0,100)g[q].cl(); up(q,0,100){ up(w,0,min(15,100-q)){ if(Pos>j&&w!=a.v[Pos])continue; if(Pos==j&&w>=a.v[Pos])continue; g[q+w].a+=f[q].a,g[q+w].b+=f[q].b+w*f[q].a; } } up(q,0,100)f[q]=g[q]; //cout<<p<<endl; //up(q,0,89)if(f[q].a)cout<<"!!! "<<f[q].a<<endl; } up(p,0,100)g[p].cl(); up(p,val[l],100) if(!((p-val[l])&15)) g[(p-val[l])>>4].a+=f[p].a,g[(p-val[l])>>4].b+=f[p].b; up(p,0,100)f[p]=g[p]; } res+=f[0].b; //cout<<i<<" "<<j<<" "<<f[0].a<<endl; //res+=f[0].a; } } cout<<res; } int main(){ //freopen("sum.in","r",stdin),freopen("sum.out","w",stdout); slv(); return 0; }