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.*;
import java.util.*;

public class EMain {
    String noResultMessage = "NoResult";
    Parser in = new Parser();
    PrintWriter out;

    long n = in.nextLong();
    int k = in.nextInteger();


    Matrix[] upRow(Matrix[] row){
        Matrix[] suffix = new Matrix[k];
        suffix[0] = Matrix.oneMatrix(k+1);
        for(int i = 1; i < k; ++i){
            suffix[i] = Matrix.mul(suffix[i-1], row[i-1]);
        }
        Matrix[] prefix = new Matrix[k];
        prefix[k-1] = row[k-1];
        for(int i = k-2; i>=0; --i){
            prefix[i] = Matrix.mul(row[i], prefix[i+1]);
        }
        Matrix[] result = new Matrix[k];
        for(int i = 0; i < k; ++i){
            result[i] = Matrix.mul(prefix[i], suffix[i]);
        }
        return result;
    }

    public void solve() {

        Matrix[][] matrixes = new Matrix[100][k];

        for(int i = 0; i < k; ++i){
            Matrix m = Matrix.oneMatrix(k + 1);
            matrixes[0][i] = m;
            for(int j = 0; j <= k; ++j){
                m.set(j, i, 1);
            }
        }
        int[] digits = new int[100];
        int index = 0;
        long limit = n;
        digits[index++] = (int) (limit % k);
        for(int row = 1; row < 100; ++row){
            limit /= k;
            if(limit == 0)break;
            digits[index++] = (int) (limit % k);
            matrixes[row] = upRow(matrixes[row-1]);
        }

        Matrix result = Matrix.oneMatrix(k+1);
        int pos = 0;
        while(index-- > 0){
            while(digits[index]-- > 0){
                result = Matrix.mul(result, matrixes[index][pos++]);
                pos %= k;
            }
        }
        Vector vec = new Vector(k+1);
        vec.set(k, 1);
        out.println(Vector.mul(vec, result).sum());


    }

    static int MOD = (int) (1e9+7);

    static public class Matrix {
        int[][] data;

        public Matrix(int size) {
            this.data = new int[size][size];
        }

        Matrix(Matrix other) {
            int size = other.data.length;
            this.data = new int[size][];
            for(int i = 0; i < size; ++i){
                this.data[i] = Arrays.copyOf(other.data[i], size);
            }
        }
        public void set(int row, int column, int value){
            data[row][column] = value;
        }

        public static Matrix oneMatrix(int size){
            Matrix result = new Matrix(size);
            for(int i = 0; i < size; ++i){
                result.data[i][i] = 1;
            }
            return result;
        }

        public static Matrix mul(Matrix left, Matrix right){
            int size = left.data.length;
            assert size == right.data.length;
            Matrix result = new Matrix(size);
            for(int i = 0; i < size; ++i){
                for(int j = 0; j < size; ++j){
                    int val = 0;
                    for(int k = 0; k < size; ++k){
                        val += 1l * left.data[i][k] * right.data[k][j] % MOD;
                        val %= MOD;
                        val += MOD;
                        val %= MOD;
                    }
                    result.data[i][j] = val;
                }
            }
            return result;
        }

        static Matrix degree(Matrix matrix, long degree){
            Matrix result = Matrix.oneMatrix(matrix.data.length);
            while(degree > 0){
                if((degree & 1) == 1){
                    result = Matrix.mul(result, matrix);
                }
                result = Matrix.mul(result, result);
                degree >>= 1;
            }
            return result;
        }
    }

    static public class Vector{
        int[] data;

        public Vector(int size) {
            this.data = new int[size];
        }

        Vector(Vector other) {
            this.data = Arrays.copyOf(other.data, other.data.length);
        }

        public void set(int pos, int val){
            data[pos] = val;
        }

        int get(int pos){
            return data[pos];
        }

        public int sum(){
            long sum = 0;
            for(int i : data){
                sum += i;
            }
            sum %= MOD;
            sum += MOD;
            sum %= MOD;
            return (int) sum;
        }

        public static Vector mul(Vector vec, Matrix matrix){
            int size = vec.data.length;
            assert size == matrix.data.length;
            Vector result = new Vector(size);
            for(int i = 0; i < size; ++i){
                int val = 0;
                for(int j = 0; j < size; ++j){
                    val += 1l * vec.data[j] * matrix.data[j][i] % MOD;
                    val += MOD;
                    val %= MOD;
                }
                result.data[i] = val;
            }
            return result;
        }
    }

    static public class Parser{
        Scanner scanner;

        public Parser() {
            scanner = new Scanner(System.in).useLocale(Locale.ENGLISH);
        }

        public Parser(String str) {
            scanner = new Scanner(str).useLocale(Locale.ENGLISH);
        }

        long nextLong(){
            return scanner.nextLong();
        }

        int nextInteger(){
            return scanner.nextInt();
        }

        double nextDouble(){
            return scanner.nextDouble();
        }

        String nextLine(){
            return scanner.nextLine();
        }

        String next(){
            return scanner.next();
        }

        int[] nextIntegers(int count){
            int[] result = new int[count];
            for(int i = 0; i < count; ++i){
                result[i] = nextInteger();
            }
            return result;
        }

        long[] nextLongs(int count){
            long[] result = new long[count];
            for(int i = 0; i < count; ++i){
                result[i] = nextLong();
            }
            return result;
        }

        int[][] nextIntegers(int fields, int count){
            int[][] result = new int[fields][count];
            for(int c = 0; c < count; ++c){
                for(int i = 0; i < fields; ++i){
                    result[i][c] = nextInteger();
                }
            }
            return result;
        }
    }

    void noResult(){
        throw new NoResultException();
    }

    void noResult(String str){
        throw new NoResultException(str);
    }

    void run(){
        try{
            ByteArrayOutputStream outStream = new ByteArrayOutputStream();
            out = new PrintWriter(outStream);
            solve();
            out.close();
            System.out.print(outStream.toString());
        } catch (NoResultException exc){
            System.out.print(null == exc.response ? noResultMessage : exc.response);
        }
    }

    public static void main(String[] args) {
        new EMain().run();
    }

    public static class NoResultException extends RuntimeException{
        private String response;

        public NoResultException(String response) {
            this.response = response;
        }

        public NoResultException() {
        }
    }
}