#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
	int mx,p,m,n;
	const int N=3505,mo=1e9+7,inv2=(mo+1)/2;
	char a[N];
	ll b[N],f[N][2][2],g[N][2][2],ans;
	void work()
	{
		scanf("%d%d",&p,&m);
		scanf("%s",a+1);
		n=strlen(a+1);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=mx;j++)
				b[j]*=10;
			b[1]+=a[i]-'0';
			mx=max(mx,1);
			for(int i=1;i<=mx;i++)
				if(b[i]>=p)
				{
					b[i+1]+=b[i]/p,b[i]%=p;
					mx=max(mx,i+1);
				}
		}
		f[0][0][1]=1;
		for(int i=mx;i;i--)
		{
			memcpy(g,f,sizeof(f)),memset(f,0,sizeof(f));
			for(int j=0;j<=mx-i+1;j++)
			{
				f[j][0][0]=(g[j][0][0]*p%mo*(p+1)%mo+g[j][0][1]*b[i]%mo*(b[i]+1)%mo+g[j][1][0]*p%mo*(p-1)%mo+g[j][1][1]*b[i]%mo*(2*p%mo-b[i]-1)%mo)*inv2%mo;
				f[j][0][1]=(g[j][0][1]*(b[i]+1)%mo+g[j][1][1]*(p-b[i]-1)%mo)%mo;
				f[j+1][1][0]=(g[j][0][0]*p%mo*(p-1)%mo+g[j][0][1]*b[i]%mo*(b[i]-1)%mo+g[j][1][0]*p%mo*(p+1)%mo+g[j][1][1]*b[i]%mo*(2*p%mo-b[i]+1)%mo)*inv2%mo;
				f[j+1][1][1]=(g[j][0][1]*b[i]%mo+g[j][1][1]*(p-b[i])%mo)%mo;
			}	
		}
		for(int j=m;j<=mx;j++)
			ans=(ans+f[j][0][0]+f[j][0][1])%mo;
		printf("%lld\n",ans);
	}
}
int main()
{
	FGF::work();
	return 0;
}