package main

import (
	"fmt"
)

const MOD = 1000000007

type Matrix struct {
	mat [31][31]int64
}

func mul(A, B *Matrix, k int) *Matrix {
	C := &Matrix{}
	for i := 0; i <= k; i++ {
		for l := 0; l <= k; l++ {
			if A.mat[i][l] == 0 {
				continue
			}
			for j := 0; j <= k; j++ {
				C.mat[i][j] = (C.mat[i][j] + A.mat[i][l]*B.mat[l][j]) % MOD
			}
		}
	}
	return C
}

func shift(M *Matrix, c int, k int) *Matrix {
	res := &Matrix{}
	for i := 0; i <= k; i++ {
		for j := 0; j <= k; j++ {
			if i < k && j < k {
				res.mat[i][j] = M.mat[(i-c%k+k)%k][(j-c%k+k)%k]
			} else if i == k && j < k {
				res.mat[i][j] = M.mat[k][(j-c%k+k)%k]
			} else if i < k && j == k {
				res.mat[i][j] = M.mat[(i-c%k+k)%k][k]
			} else {
				res.mat[i][j] = M.mat[k][k]
			}
		}
	}
	return res
}

func mulVec(V []int64, M *Matrix, k int) []int64 {
	res := make([]int64, k+1)
	for j := 0; j <= k; j++ {
		var sum int64 = 0
		for i := 0; i <= k; i++ {
			sum = (sum + V[i]*M.mat[i][j]) % MOD
		}
		res[j] = sum
	}
	return res
}

func main() {
	var n int64
	var k int
	if _, err := fmt.Scan(&n, &k); err != nil {
		return
	}

	digits := []int{}
	temp := n
	for temp > 0 {
		digits = append(digits, int(temp%int64(k)))
		temp /= int64(k)
	}

	U0 := &Matrix{}
	for i := 0; i <= k; i++ {
		U0.mat[i][i] = 1
		U0.mat[i][0] = 1
	}

	B := make([]*Matrix, len(digits))
	B[0] = U0

	for m := 0; m < len(digits)-1; m++ {
		res := shift(B[m], 0, k)
		for c := 1; c < k; c++ {
			res = mul(res, shift(B[m], c, k), k)
		}
		B[m+1] = res
	}

	V := make([]int64, k+1)
	V[k] = 1

	prefixSum := 0
	for m := len(digits) - 1; m >= 0; m-- {
		d := digits[m]
		if d > 0 {
			for c := 0; c < d; c++ {
				shiftedB := shift(B[m], (prefixSum+c)%k, k)
				V = mulVec(V, shiftedB, k)
			}
			prefixSum = (prefixSum + d) % k
		}
	}

	var total int64 = 0
	for i := 0; i <= k; i++ {
		total = (total + V[i]) % MOD
	}

	fmt.Println(total)
}