#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4005,mod=1e9+7;
int n,p,t;
ll ans,f[N][2][2],g[N][2][2];
vector<int>a;
int S1(int l,int r){return l>r?0:1ll*(l+r+2)*(r-l+1)/2%mod;}
int S2(int l,int r){return l>r?0:1ll*(2*p-2-l-r)*(r-l+1)/2%mod;}
void Add(ll&x,ll y){x=(x+y)%mod;}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string s;cin>>p>>t>>s;
	if(!s[0])return cout<<"0\n",0;
	while(s.size()) {
		ll x=0;string t="";
		for(char i:s) {
			x=x*10+i-'0';
			if(t.size()||x>=p)t+=x/p+'0';
			x%=p;
		}s=t,a.push_back(x);
	}
	f[0][1][0]=1,n=a.size();
	for(int i=0;i<n;i++) {
		memcpy(g,f,sizeof(g)),memset(f,0,sizeof(f));
		int w=a[i];
		for(int j=0;j<=i;j++) {
			for(int k=0;k<2;k++) {
				for(int l=0;l<2;l++) {
					if(!g[j][k][l])continue;
					ll v=g[j][k][l];
					Add(f[j][0][0],v*S1(w+k-l,p-1-l));
					Add(f[j][1][0],v*S1(-l,w-(!k)-l));
					Add(f[j+1][0][1],v*S2(w+k-l,p-1-l));
					Add(f[j+1][1][1],v*S2(-l,w-(!k)-l));
				}
			}
		}
	}
	for(int i=t;i<=n;i++)Add(ans,f[i][1][0]);
	cout<<ans<<'\n';
	return 0;
}