#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
inline int add(int a, int b) { return a += b, a >= MOD ? a - MOD : a; }
inline int del(int a, int b) { return a -= b, a < 0 ? a + MOD : a; }
inline int mul(int a, int b) { return 1LL * a * b % MOD; }
const int MAXN = 3400;
char N[MAXN];
int dp[MAXN][MAXN][2][2];
int A[MAXN], p, a, l, n, ans;
inline int turn(char *ch, int P) {
  long long tmp = 0;
  for (int i = l; i; i--) tmp = tmp * 10 + ch[i], ch[i] = tmp / P, tmp %= P;
  while (l && !ch[l]) l--;
  return tmp;
}
inline int getp(int c, int r, int nr) {
  if (r)
    return del(p, getp(c, 0, nr));
  else
    return c - nr + 1;
}
inline int gets(int c, int r, int nr) {
  if (r) return del(mul(c + 1, p), gets(c, 0, nr));
  if (c & 1)
    return del(mul(c + 2, (c + 1) >> 1), mul(nr, c + 1));
  else
    return del(mul(c + 1, (c + 2) >> 1), mul(nr, c + 1));
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> p >> a >> (N + 1);
  l = strlen(N + 1);
  for (int i = 1; i <= l; i++) N[i] = N[i] & 15;
  reverse(N + 1, N + l + 1);
  while (l) A[++n] = turn(N, p);
  reverse(A + 1, A + n + 1);
  if (a > n) return cout << 0 << endl, 0;
  dp[1][0][1][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= a; j++)
      for (int k = 0; k <= 1; k++)
        for (int l = 0; l <= 1; l++)
          if (dp[i][j][k][l]) {
            int tmp = dp[i][j][k][l];
            for (int cur = 0; cur <= 1; cur++) {
              int tmp_ = min(j + cur, a);
              if (!k)
                dp[i + 1][tmp_][k][cur] =
                    add(dp[i + 1][tmp_][k][cur], mul(tmp, gets(p - 1, l, cur)));
              else {
                dp[i + 1][tmp_][k][cur] =
                    add(dp[i + 1][tmp_][k][cur], mul(tmp, getp(A[i], l, cur)));
                if (A[i])
                  dp[i + 1][tmp_][0][cur] =
                      add(dp[i + 1][tmp_][0][cur],
                          mul(tmp, gets(A[i] - 1, l, cur)));
              }
            }
          }
  ans = add(dp[n + 1][a][0][0] % MOD, dp[n + 1][a][1][0] % MOD);
  cout << ans << endl;
  return 0;
}
