Assume that s_k(n) equals the sum of digits of number n in the k-based notation. For example, s₂(5) = s₂(101₂) = 1 + 0 + 1 = 2, s₃(14) = s₃(112₃) = 1 + 1 + 2 = 4.

The sequence of integers a₀, ..., a_n - 1 is defined as $\text{[math]}$ . Your task is to calculate the number of distinct subsequences of sequence a₀, ..., a_n - 1. Calculate the answer modulo 10⁹ + 7.

Sequence a₁, ..., a_k is called to be a subsequence of sequence b₁, ..., b_l, if there is a sequence of indices 1 ≤ i₁ < ... < i_k ≤ l, such that a₁ = b_i₁, ..., a_k = b_{i_k}. 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 ≤ 10¹⁸, 2 ≤ k ≤ 30).

Output

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

Note

In the first sample the sequence a_i 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 a_i 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 2⁷ = 128 such sequences.

Subsequences Return

Examples