#include<bits/stdc++.h> using namespace std; #define int long long #define ll unsigned long long #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} int todit(char c){return !c?0:c>='0'&&c<='9'?c-'0':c-'A'+10;} const int MAXN=410,N=40,M=210; int n,m,k,ans,a[MAXN],w[MAXN]; char c[MAXN]; ll f[N][M],g[N][M],F[MAXN][N],G[MAXN][N]; void slv(){ n=read(),k=read(); scanf("%s",c+1); reverse(c+1,c+n+1); n+=k; for(int i=1;i<=n;i++) for(int j=max(1ll,i-k+1);j<=i;j++)a[i]+=todit(c[j])*15; for(int i=1;i<=n;i++){ a[i+1]+=a[i]>>4,a[i]&=15; if(a[i+1]&&i+1>n)n++; } if(n%k)n+=k-n%k; m=n/k; reverse(a+1,a+n+1); for(int p=1;p<=m;p++){ for(int i=1;i<=k;i++)w[i]=p*15; for(int i=k;i>1;i--)w[i-1]+=w[i]/16,w[i]%=16; for(int t=1;t<=n;t++){ memset(F,0,sizeof(F)),memset(G,0,sizeof(G)); F[0][0]=1; for(int i=1;i<=k;i++){ memset(f,0,sizeof(f)),memset(g,0,sizeof(g)); f[0][0]=1; for(int j=1;j<=m;j++){ int now=(j-1)*k+i; for(int o=0;o<16;o++)if((now<t&&o==a[now])||(now==t&&o<a[now])||(now>t)){ for(int s=o;s<16*m;s++) f[j][s]+=f[j-1][s-o],g[j][s]+=f[j-1][s-o]*o+g[j-1][s-o]; } } for(int x=0;x<m;x++)for(int y=0;y<m;y++)if(w[i]+16*x-y>=0&&w[i]+16*x-y<16*m){ F[i][y]+=F[i-1][x]*f[m][w[i]+16*x-y]; G[i][y]+=F[i-1][x]*g[m][w[i]+16*x-y]+G[i-1][x]*f[m][w[i]+16*x-y]; } } ans+=G[k][0]; } } printf("%llu",ans); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; } /* 1 0 0 1 1 0 1 2 0 1 3 224 1 4 3495 1 5 3976 2 0 0 2 1 0 2 2 0 2 3 0 2 4 360 2 5 136 */