import java.io.*;
import java.math.BigInteger;

public class binomial_count_vi {

    final static long MOD = 1000000007;

    public static void solve(Input in, PrintWriter out) throws IOException {
        int p = in.nextInt();
        int alpha = in.nextInt();
        BigInteger A = new BigInteger(in.next()), bp = BigInteger.valueOf(p);
//        A = BigInteger.TEN.pow(1000);
        long time0 = System.currentTimeMillis();
        int[] a = new int[3500];
        for (int i = 0; i < a.length && A.signum() > 0; ++i) {
            a[i] = A.mod(bp).intValue();
            A = A.divide(bp);
        }
        System.err.println(System.currentTimeMillis() - time0);
        int aLen = a.length;
        while (aLen > 0 && a[aLen - 1] == 0) {
            --aLen;
        }
        long[][] d = new long[4][a.length + 2];
        long[][] d1 = new long[4][a.length + 2];
        d[0][0] = 1L;
        for (int it = 0; it < aLen; ++it) {
            long[] cnt = new long[12];
            for (int c = 0; c < 2; ++c) {
                cnt[c] += cnt(0, a[it], c, p);
                cnt[4 + c] += cnt(a[it], a[it] + 1, c, p);
                cnt[8 + c] += cnt(a[it] + 1, p, c, p);
                cnt[2 + c] += cnt(p, p + a[it], c, p);
                cnt[4 + 2 + c] += cnt(p + a[it], p + a[it] + 1, c, p);
                cnt[8 + 2 + c] += cnt(p + a[it] + 1, 2 * p, c, p);
            }
            for (int i = 0; i < cnt.length; ++i) {
                cnt[i] %= MOD;
            }
            for (int i = 0; i <= it; ++i) {
                for (int u = 0; u < 4; ++u) {
                    if (d[u][i] == 0) {
                        continue;
                    }
                    for (int t = u & 1; t < cnt.length; t += 2) {
                        int v = 2 * mod(u / 2, t / 4) + ((t / 2) & 1);
                        d1[v][i + (v & 1)] += d[u][i] * cnt[t];
                    }
                }
            }
            for (int i = 0; i < d.length; ++i) {
                for (int j = 0; j <= it + 1; ++j) {
                    d[i][j] = d1[i][j] % MOD;
                    d1[i][j] = 0;
                }
            }
        }
        long ans = 0;
        for (int j = alpha; j < d[0].length; ++j) {
                ans += d[0][j];
        }
        out.println(ans % MOD);
        System.err.println(System.currentTimeMillis() - time0);
    }

    private static int mod(int u, int um) {
        return um == 0 ? 0 : um == 2 ? 1 : u;
    }

    private static long cnt(int from, int to, int c, long p) {
        return cnt(to - c, p) - cnt(from - c, p);
    }

    private static long cnt(long ai, long p) {
        ai = Math.min(ai, 2 * p);
        ai = Math.max(ai, 0);
        return ai * (ai + 1) / 2 - (ai > p ? (ai - p) * (ai - p + 1) : 0);
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}