For a given prime integer p and integers α, A calculate the number of pairs of integers (n, k), such that 0 ≤ k ≤ n ≤ A and <image> is divisible by pα. 

As the answer can be rather large, print the remainder of the answer moduly 109 + 7.

Let us remind you that <image> is the number of ways k objects can be chosen from the set of n objects.

Input

The first line contains two integers, p and α (1 ≤ p, α ≤ 109, p is prime). 

The second line contains the decimal record of integer A (0 ≤ A < 101000) without leading zeroes.

Output

In the single line print the answer to the problem.

Examples

Input

2 2
7


Output

3


Input

3 1
9


Output

17


Input

3 3
9


Output

0


Input

2 4
5000


Output

8576851

Note

In the first sample three binominal coefficients divisible by 4 are <image>, <image> and <image>.
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;

public class cf582d
{
    public static final int INF = 1000000007;
    public static final int MAXN = 3333;

    public static int add(int a, int b)
    {
        a += b; if (a >= INF) a -= INF;
        return a;
    }
    public static int sub(int a, int b)
    {
        a -= b; if (a < 0) a += INF;
        return a;
    }
    public static int mul(int a, int b)
    {
        return (int) ((long) a * b % INF);
    }
    public static int pwr(int a, int b)
    {
        int res = 1;
        while(b > 0)
        {
            if ((b & 1) != 0) res = mul(res, a);
            a = mul(a, a);
            b >>= 1;
        }
        return res;
    }
    public static int sum(int l, int r)
    {
        return (int)((long) (r - l + 1) * (r + l) / 2 % INF);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter output = new PrintWriter(new BufferedOutputStream(System.out));
        StringTokenizer st = new StringTokenizer(input.readLine());
        int P = Integer.parseInt(st.nextToken()), E = Integer.parseInt(st.nextToken());
        BigInteger A = new BigInteger(input.readLine());
        BigInteger bP = BigInteger.valueOf(P);
        ArrayList<Integer> arr = new ArrayList<Integer>();
        while(A.compareTo(BigInteger.ZERO) > 0)
        {
            arr.add(A.mod(bP).intValue());
            A = A.divide(bP);
        }
        int N = arr.size();
        if (E > N)
        {
            System.out.println("0");
            System.exit(0);
        }
        int ans = 0;
        int[][][][] dp = new int[2][2][2][MAXN];
        dp[1][1][0][0] = 1;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    for (int m = 0; m <= i; m++)
                    {
                        dp[0][j][k][m] = dp[1][j][k][m];
                        dp[1][j][k][m] = 0;
                    }
                }
            }
            //dp[a][b][c]
            //a: in the last digit that differed, who was larger? BIG or arr?
            //b: did we just have a carry?
            //c: how many carries have we had so far?
            int d = arr.get(i);
            // System.out.println("d = " + d);
            for (int k = 0; k <= i; k++)
            {
                int ways = 0;
                //case 1: l < d, n carry.
                ways = 0;
                ways = add(ways, mul(add(dp[0][0][0][k], dp[0][1][0][k]), sum(1, d)));
                ways = add(ways, mul(add(dp[0][0][1][k], dp[0][1][1][k]), sum(0, d - 1)));
                dp[1][1][0][k] = add(dp[1][1][0][k], ways);
                //case 2: l = d, n carry.
                ways = 0;
                ways = add(ways, mul(dp[0][1][0][k], d + 1));
                ways = add(ways, mul(dp[0][1][1][k], d));
                dp[1][1][0][k] = add(dp[1][1][0][k], ways);
                ways = 0;
                ways = add(ways, mul(dp[0][0][0][k], d + 1));
                ways = add(ways, mul(dp[0][0][1][k], d));
                dp[1][0][0][k] = add(dp[1][0][0][k], ways);
                //case 3: l > d, n carry.
                ways = 0;
                ways = add(ways, mul(add(dp[0][0][0][k], dp[0][1][0][k]), sum(d + 2, P)));
                ways = add(ways, mul(add(dp[0][0][1][k], dp[0][1][1][k]), sum(d + 1, P - 1)));
                dp[1][0][0][k] = add(dp[1][0][0][k], ways);
                //###################################################################DIVIDING POINT####################################################
                //case 4: l < d, y carry.
                ways = 0;
                ways = add(ways, mul(add(dp[0][0][0][k], dp[0][1][0][k]), sum(P - d, P - 1)));
                ways = add(ways, mul(add(dp[0][0][1][k], dp[0][1][1][k]), sum(P - (d - 1), P)));
                dp[1][1][1][k + 1] = add(dp[1][1][1][k + 1], ways);
                //case 5: l = d, y carry.
                ways = 0;
                ways = add(ways, mul(dp[0][1][0][k], P - (d + 1)));
                ways = add(ways, mul(dp[0][1][1][k], P - d));
                dp[1][1][1][k + 1] = add(dp[1][1][1][k + 1], ways);
                ways = 0;
                ways = add(ways, mul(dp[0][0][0][k], P - (d + 1)));
                ways = add(ways, mul(dp[0][0][1][k], P - d));
                dp[1][0][1][k + 1] = add(dp[1][0][1][k + 1], ways);
                //case 6: l > d, y carry.
                ways = 0;
                ways = add(ways, mul(add(dp[0][0][0][k], dp[0][1][0][k]), sum(0, P - (d + 2))));
                ways = add(ways, mul(add(dp[0][0][1][k], dp[0][1][1][k]), sum(1, P - (d + 1))));
                dp[1][0][1][k + 1] = add(dp[1][0][1][k + 1], ways);
            }
        }
        for (int i = E; i <= N; i++)
        {
            ans = add(ans, dp[1][1][0][i]);
        }
        //what we're really saying is that the # of carries must be >= E.
        System.out.println(ans);
        System.exit(0);
    }
}
