#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define int long long
using namespace std;
const int N=4e3,P=1e9+7;
int n,a[N],sl,x,y,p,k,f[2][N][2][2],c01,c00,c11,c10,as,o;
char s[N];
signed main()
{
	scanf("%lld%lld%s",&p,&k,s+1);sl=strlen(s+1);
	f(j,1,sl)
	{
		f(i,0,n)a[i]*=10;a[0]+=s[j]-'0';
		f(i,0,n)a[i+1]+=a[i]/p,a[i]%=p;
		while(a[n+1])++n,a[n+1]+=a[n]/p,a[n]%=p;
	}
	f[0][0][1][0]=1;
	df(i,n,0)
{
	o^=1;
	memset(f[o],0,sizeof(f[o]));
	f(j,0,n)
	{
		c00=f[o^1][j][0][0];c01=f[o^1][j][0][1];c10=f[o^1][j][1][0];c11=f[o^1][j][1][1];
//		cout<<i<<j<<c01<<c11<<'\n';
		f[o][j][0][0]+=(p*(p+1)/2%P*c00+a[i]*(a[i]+1)/2%P*c10)%P;
		f[o][j+1][0][0]=((a[i]*(a[i]+1)/2+(p-1-a[i])*a[i])%P*c11+p*(p-1)/2%P*c01)%P;
		f[o][j][0][1]+=(p*(p-1)/2%P*c00+a[i]*(a[i]-1)/2%P*c10)%P;
		f[o][j+1][0][1]=((a[i]*(a[i]-1)/2+(p-a[i]+1)*a[i])%P*c11+p*(p+1)/2%P*c01)%P;
		f[o][j][1][0]+=(a[i]+1)*c10%P;
		f[o][j+1][1][0]=(p-a[i]-1)*c11%P;
		f[o][j][1][1]+=a[i]*c10%P;
		f[o][j+1][1][1]=(p-a[i])*c11%P;
	}
}
//	f(i,0,n)f(j,1,n)f(k,0,1)f(l,0,1)cout<<f[i][j][k][l]<<' ';
	f(i,k,n)as=(as+f[o][i][1][0]+f[o][i][0][0])%P;
	cout<<as;
	return 0;
}//2511194685486342801