func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1e9 + 7;   const int SIZE = 1e6 + 10;   char A[SIZE];   long long d[SIZE];   int len;   vector<long long> D;   long long dp[2][4000][2][2];   void ADD(long long &x, long long v) { x = (x + v) % MOD; }   long long CC(long long x) { return x * (x - 1) / 2 % MOD; }   long long con(long long x, long long y) {     if (x > y) return 0;     return (x + y) * (y - x + 1) / 2 % MOD;   }   int main() {     int p, a;     scanf( %d%d , &p, &a);     scanf( %s , (A));     len = strlen(A);     for (int i = 0; i < (len); ++i) {       d[len - 1 - i] = A[i] -  0 ;     }     int top = len - 1;     while (top >= 0) {       long long r = 0;       for (int i = top; i >= 0; i--) {         r *= 10;         d[i] += r;         r = d[i] % p;         d[i] /= p;       }       D.push_back(r);       while (top >= 0 && d[top] == 0) top--;     }     if (a >= ((int)(D).size())) return 0 * puts( 0 );     int now = 0, nxt = 1;     dp[now][0][1][0] = 1;     for (int i = ((int)(D).size()) - 1; i >= 0; i--) {       memset((dp[nxt]), 0, sizeof((dp[nxt])));       for (int j = 0; j < (a + 1); ++j) {         ADD(dp[nxt][j][1][0], dp[now][j][1][1] * (p - 1 - D[i]));         ADD(dp[nxt][min(j + 1, a)][1][1], dp[now][j][1][1] * (p - D[i]));         ADD(dp[nxt][j][0][0], dp[now][j][1][1] * con(p - D[i], p - 1));         ADD(dp[nxt][min(j + 1, a)][0][1],             dp[now][j][1][1] * con(p - D[i] + 1, p));         ADD(dp[nxt][j][1][0], dp[now][j][1][0] * (D[i] + 1));         ADD(dp[nxt][min(j + 1, a)][1][1], dp[now][j][1][0] * D[i]);         ADD(dp[nxt][j][0][0], dp[now][j][1][0] * con(1, D[i]));         ADD(dp[nxt][min(j + 1, a)][0][1], dp[now][j][1][0] * con(1, D[i] - 1));         ADD(dp[nxt][j][0][0], dp[now][j][0][1] * con(1, p - 1));         ADD(dp[nxt][min(j + 1, a)][0][1], dp[now][j][0][1] * con(1, p));         ADD(dp[nxt][j][0][0], dp[now][j][0][0] * con(1, p));         ADD(dp[nxt][min(j + 1, a)][0][1], dp[now][j][0][0] * con(1, p - 1));       }       swap(now, nxt);     }     long long an = 0;     for (int j = 0; j < (2); ++j) ADD(an, dp[now][a][j][0]);     cout << an;     return 0;   }   