//incomplete
#include<bits/stdc++.h>
using namespace std;

constexpr long long mod=1000000007;
constexpr int maxn=3400;

char A[maxn];
long long p,B[maxn];
int a,dp[maxn][maxn][2][2];//<200M

int main()
{
	int i,j,k=0,n;
	long long nAns=0;
	cin>>p>>a>>A;
	n=strlen(A);
	for(i=0;i<n;i++)
	{
		for(j=0;j<=k;j++) B[j]*=10;
		B[0]+=A[i]-'0';
		for(j=0;j<k;j++) if(B[j]>=p) B[j+1]+=B[j]/p,B[j]%=p;
		for(;B[k]>=p;k++) B[k+1]+=B[k]/p,B[k]%=p;
	}
	if(a>k)
	{
		cout<<0<<endl;
		return 0;
	}
	dp[k+1][0][0][1]=1;
	for(i=k;i>=0;i--)
	{
		long long lp=(p+1)*p/2%mod,lb=(B[i]+1)*B[i]/2%mod;
		long long gep=(p-1)*p/2%mod,lbp=B[i]*(p*2-B[i]-1)/2%mod;
		long long alb=(B[i]-1)*B[i]/2%mod,alpb=B[i]*(p*2-B[i]+1)/2%mod;
		for(j=0;j<=k-i+1;j++)
		{
			auto pre=dp[i+1][j];
			dp[i][j][0][0]=(pre[0][0]*lp+pre[0][1]*lb+pre[1][0]*gep+pre[1][1]*lbp)%mod;
			dp[i][j][0][1]=(pre[0][1]*(B[i]+1)+pre[1][1]*(p-B[i]-1))%mod;
			dp[i][j+1][1][0]=(pre[0][0]*gep+pre[0][1]*alb+pre[1][0]*lp+pre[1][1]*alpb)%mod;
			dp[i][j+1][1][1]=(pre[0][1]*B[i]+pre[1][1]*(p-B[i]))%mod;
		}
	}
	for(i=a;i<=k;i++) nAns+=dp[0][i][0][0]+dp[0][i][0][1];
	cout<<nAns%mod<<endl;
	return 0;
}