#include<bits/stdc++.h>
using namespace std;
const int N=4e3+5,mod=1e9+7;
int p,a,m,A[N],len,x[N],lst,cur,f[2][N][2][2],ans;
char s[N];
signed main(){
	scanf("%d%d%s",&p,&a,s+1),len=strlen(s+1);
	if(a>4e3) puts("0"),exit(0);
	for(int i=1;i<=len;i++) A[len-i+1]=s[i]-'0';
	while(len){
		long long cur=0;
		for(int i=len;i>=1;i--) cur=cur*10+A[i],A[i]=cur/p,cur%=p;
		x[++m]=cur;
		if(!A[len]) len--;
	}
	f[cur=1][0][0][1]=1;
	for(int i=m;i>=1;i--){
		swap(cur,lst),memset(f[cur],0,sizeof(f[cur]));
		int c1=1ll*p*(p+1)/2%mod,c2=1ll*(x[i]+1)*x[i]/2%mod;
		int c3=1ll*(p-1)*p/2%mod,c4=1ll*x[i]*(p*2-x[i]-1)/2%mod;
		int c5=1ll*(x[i]-1)*x[i]/2%mod,c6=1ll*x[i]*(p*2-x[i]+1)/2%mod;
		for(int j=0;j<=m-i+1;j++){
			int f0=f[lst][j][0][0],f1=f[lst][j][0][1];
			int f2=f[lst][j][1][0],f3=f[lst][j][1][1];
			f[cur][j][0][0]=(1ll*f0*c1%mod+1ll*f1*c2%mod+1ll*f2*c3%mod+1ll*f3*c4%mod)%mod;
			f[cur][j][0][1]=(1ll*(x[i]+1)*f1%mod+1ll*(p-x[i]-1)*f3%mod)%mod;
			f[cur][j+1][1][0]=(1ll*f0*c3%mod+1ll*f1*c5%mod+1ll*f2*c1%mod+1ll*f3*c6%mod)%mod;
			f[cur][j+1][1][1]=(1ll*f1*x[i]%mod+1ll*f3*(p-x[i])%mod)%mod;
		}
	}
	for(int i=a;i<=m;i++)
		ans=((ans+f[cur][i][0][0])%mod+f[cur][i][0][1])%mod;
	printf("%d\n",ans);
	return 0;
}