// LUOGU_RID: 113001927
#include<bits/stdc++.h>
using namespace std;
const int N=3505,mod=1e9+7;
int f[N][N][2][2],t[N];
long long n,p,m,tot,a[N],ans;
char s[N];
signed main(){
    cin>>p>>m>>(s+1);tot=strlen(s+1);
    for(int i=1;i<=tot;i++)t[i]=s[tot-i+1]-'0';
    while(tot){
        long long sum=0;
        for(int i=tot;i;i--){
            sum=sum*10+t[i],t[i]=sum/p,sum%=p;
            if(!t[i]&&i==tot)tot--;
        }
        a[++n]=sum;
    }
    f[n+1][0][1][0]=1;
    for(int i=n;i;i--){
        long long v1=(p+1)*p/2%mod,v2=(a[i]+1)*a[i]/2%mod,v3=(p-1)*p/2%mod,v4=a[i]*(2*p-a[i]-1)/2%mod,v5=a[i]*(a[i]-1)/2%mod,v6=a[i]*(2*p-a[i]+1)/2%mod;
        for(int j=0;j<=n-i;j++){
            long long f1=f[i+1][j][0][0],f2=f[i+1][j][1][0],f3=f[i+1][j][0][1],f4=f[i+1][j][1][1];
            f[i][j][0][0]=(f1*v1%mod+f2*v2%mod+f3*v3%mod+f4*v4%mod)%mod;
            f[i][j][1][0]=(f2*(a[i]+1)%mod+f4*(p-1-a[i])%mod)%mod;
            f[i][j+1][0][1]=(f1*v3%mod+f2*v5%mod+f3*v1%mod+f4*v6%mod)%mod;
            f[i][j+1][1][1]=(f2*a[i]%mod+f4*(p-a[i])%mod)%mod;
        }
    }
    for(int i=m;i<=n;i++)ans=(ans+f[1][i][0][0]+f[1][i][1][0])%mod;
    cout<<ans;
    return 0;
}