Oobleck Boxes

/*

This question is taken from hackerrank.com

The people of Trennwand are not simple or one-dimensional. In fact, they make use of an unlimited number of dimensions. This might be confusing for visitors, but it makes storage much more efficient for residents. Many people in Trennwand collect Oobleck, a strange substance which can be stored very effectively in multi-dimensional boxes. A box of length M and dimensions d can store Md units of Oobleck. For example, if M = 2, then one could create boxes that store 1,2,4,8,… units of Oobleck.

oobleck 1 to 5 dimensions

Mathenius, the king of Trennwand, decides to purchase a large amount of Oobleck for his new Oobleck skiing resort. He needs exactly N units of Oobleck, in any number of boxes. The Royal Oobleck Store has an unlimited supply of boxes of Oobleck, but they are all M long on each side.

Challenge
The king, being rather mathematical, is interested in the total number of ways (S) he can buy the exact amount (N) of Oobleck from the store. Remember, the store sells any number of boxes that each contain Md units of Oobleck, where d is any non-negative integer.

The king asks you to calculate S. If you are successful, he will give you season lift tickets to his new Oobleck Skiing Resort.

Input
There will be one line of input which will contain two integers N and M. N is the exact number of Oobleck units the king needs. M is the length of the Oobleck boxes that the store sells.

Output
Output S, the total number of ways the Oobleck can be purchased. Since S can be large, output S % 1000000007

Constraints
1 < m <= n < 1000000

Sample Input
7 2

Sample Output
6

Explanation
If M=2, you can buy boxes that contain 1, 2 or 4 units of Oobleck in them. There are the 6 possible ways 7 units of Oobleck can be purchased with those boxes:
7 = 7 * 1
7 = 5 * 1 + 1 * 2
7 = 3 * 1 + 2 * 2
7 = 3 * 1 + 1 * 4
7 = 1 * 1 + 3 * 2
7 = 1 * 1 + 1 * 2 + 1 * 4
*/


import java.util.Scanner;

public class Solution {

    private int unitsN = 0;
    private int lengthM = 0 ;
    private int dimensions = 0;
    private long solutions = 0;
    private int[] volumes;
   
    public void initialise()
    {
        Scanner scan = new Scanner(System.in);
        unitsN = scan.nextInt();
        lengthM = scan.nextInt();
        scan.close();
        getDimensions();
        getAllVolumes();
        getSolutions(unitsN,0);
        solutions %= 1000000007;
        System.out.println(solutions);
    }
   
    private void getDimensions()
    {
        int n = 0;
        while(true)
        {
            if(Math.pow(lengthM, n+1) <= unitsN)
            {
                n = n+1;
                dimensions = n+1;
            }
            else
            {
                return;
            }
        }
    }
    public void getAllVolumes()
    {
        volumes = new int[dimensions];
        for(int i = 0 ; i<dimensions ; i++)
        {
            volumes[i] = (int) Math.pow(lengthM, i);
        }
    }
   
    public static void main(String args[])
    {
        Solution s = new Solution();
        s.initialise();
    }
    public void getSolutions(int left, int start)
    {
        if(left == 0)
        {
            solutions++;
        }
        else if(left > 0)
        {
            for(int i = start ; i < volumes.length ; i++)
            {
                if(left - volumes[i] < 0 )
                    return;
                getSolutions(left - volumes[i],i);
            }
        }
    }
}