#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n,p,a[100010],x[100010],m;
char s[100010];
int f[2][10010][2][2];
int main()
{
	scanf("%lld%lld%s",&n,&p,s+1);
	if(p>4000){
		puts("0");
		return 0;
	} 
	int len=strlen(s+1);
	for(int i=1;i<=len;i++) a[len-i+1]=s[i]-'0';
	while(len){
		ll cnt=0;
		for(int i=len;i;i--){
			cnt=cnt*10+a[i];
			a[i]=cnt/n;
			cnt%=n;
		}
		x[++m]=cnt;
		if(!a[len]) len--;
	}
	ll cnt=1,pre=0;
	f[cnt][0][0][1]=1;
	for(int i=m;i;i--){
		cnt^=pre^=cnt^=pre;
		memset(f[cnt],0,sizeof(f[cnt]));
		ll c1=(n+1)*n/2%mod;
		ll c2=(x[i]+1)*x[i]/2%mod;
		ll c3=(n-1)*n/2%mod;
		ll c4=x[i]*(n*2-x[i]-1)/2%mod;
		ll c5=(x[i]-1)*x[i]/2%mod;
		ll c6=x[i]*(n*2-x[i]+1)/2%mod;
		for(int j=0;j<m-i+1;j++){
			ll f0=f[pre][j][0][0],f1=f[pre][j][0][1];
			ll f2=f[pre][j][1][0],f3=f[pre][j][1][1];
			f[cnt][j][0][0]=(f0*c1+f1*c2+f2*c3+f3*c4)%mod;
			f[cnt][j][0][1]=((x[i]+1)*f1+(n-x[i]-1)*f3)%mod;
			f[cnt][j+1][1][0]=(f0*c3+f1*c5+f2*c1+f3*c6)%mod;
			f[cnt][j+1][1][1]=(x[i]*f1+(n-x[i])*f3)%mod;
		}
	}
	ll ans=0;
	for(int i=p;i<=m;i++){
		ans=(ans+f[cnt][i][0][0])%mod;
		ans=(ans+f[cnt][i][0][1])%mod;
	}
	printf("%lld",ans);
	return 0;
}