Problem: Assume that sk(n) equals the sum of digits of number n in the k-based notation. For example, s2(5) = s2(1012) = 1 + 0 + 1 = 2, s3(14) = s3(1123) = 1 + 1 + 2 = 4.

The sequence of integers a0, ..., an - 1 is defined as <image>. Your task is to calculate the number of distinct subsequences of sequence a0, ..., an - 1. Calculate the answer modulo 109 + 7.

Sequence a1, ..., ak is called to be a subsequence of sequence b1, ..., bl, if there is a sequence of indices 1 ≤ i1 < ... < ik ≤ l, such that a1 = bi1, ..., ak = bik. In particular, an empty sequence (i.e. the sequence consisting of zero elements) is a subsequence of any sequence.

Input

The first line contains two space-separated numbers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 30).

Output

In a single line print the answer to the problem modulo 109 + 7.

Examples

Input

4 2


Output

11


Input

7 7


Output

128

Note

In the first sample the sequence ai looks as follows: (0, 1, 1, 0). All the possible subsequences are: 

(), (0), (0, 0), (0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 1, 0), (1), (1, 0), (1, 1), (1, 1, 0).

In the second sample the sequence ai looks as follows: (0, 1, 2, 3, 4, 5, 6). The subsequences of this sequence are exactly all increasing sequences formed from numbers from 0 to 6. It is easy to see that there are 27 = 128 such sequences.

Solution (in JAVA):

Solution:
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    static final long MODULO = (long) (1e9 + 7);
    static final long BIG = Long.MAX_VALUE - Long.MAX_VALUE % MODULO;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        long n = in.nextLong();
        int k = in.nextInt();
        long pk = 1;
        int pow = 0;
        while (pk <= n / k) {
            pk *= k;
            ++pow;
        }
        matrCache = new long[pow + 1][][];
        long at = 0;
        long[] ways = new long[k + 1];
        ways[k] = 1;
        while (at < n) {
            while (at + pk <= n) {
                long[][] matr = getMatr(digitSum(at, k) % k, k, pow);
                ways = mul(matr, ways);
                at += pk;
            }
            pk /= k;
            --pow;
        }
        long res = 0;
        for (long x : ways) res += x;
        res %= MODULO;
        out.println(res);
    }

    long[][][] matrCache;

    private long[][] getMatr(int pre, int k, int pow) {
        long[][] res = matrCache[pow];
        if (res == null) {
            if (pow == 0) {
                res = new long[k + 1][k + 1];
                for (int i = 0; i < k + 1; ++i) ++res[i][i];
                for (int i = 0; i < k + 1; ++i) {
                    ++res[0][i];
                }
                --res[0][0];
            } else {
                res = new long[k + 1][k + 1];
                for (int i = 0; i < k + 1; ++i) ++res[i][i];
                for (int i = 0; i < k; ++i) {
                    res = mul(getMatr(i, k, pow - 1), res);
                }
            }
            matrCache[pow] = res;
        }
        long[][] rotated = new long[k + 1][k + 1];
        for (int i = 0; i <= k; ++i)
            for (int j = 0; j <= k; ++j) {
                int ii = (i == k) ? k : (pre + i) % k;
                int jj = (j == k) ? k : (pre + j) % k;
                rotated[ii][jj] = res[i][j];
            }
        return rotated;
    }

    private long[] mul(long[][] a, long[] b) {
        long[] c = new long[b.length];
        for (int i = 0; i < c.length; ++i) {
            long s = 0;
            for (int j = 0; j < c.length; ++j) {
                s += a[i][j] * b[j];
                if (s < 0) s -= BIG;
            }
            c[i] = s % MODULO;
        }
        return c;
    }

    private long[][] mul(long[][] a, long[][] b) {
        long[][] c = new long[b.length][b.length];
        for (int i = 0; i < c.length; ++i) {
            for (int k = 0; k < c.length; ++k) {
                long s = 0;
                for (int j = 0; j < c.length; ++j) {
                    s += a[i][j] * b[j][k];
                    if (s < 0) s -= BIG;
                }
                c[i][k] = s % MODULO;
            }
        }
        return c;
    }

    private int digitSum(long at, int k) {
        int res = 0;
        while (at > 0) {
            res += at % k;
            at /= k;
        }
        return res;
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

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

}