거듭제곱 분할 함수의 거듭제곱

정수 $m$은 $m \ge 2$를 만족하는 고정된 정수이다. 양의 정수 $n$에 대해, $b_m(n)$은 $n$을 지수가 0 이상인 $m$의 거듭제곱들의 합으로 나타내는 방법의 수이다. 같은 항을 여러 번 쓸 수 있고, 항의 순서는 고려하지 않는다. 빈 합이 한 가지 방법이므로 $b_m(0) = 1$로 정의한다.

예를 들어, $\{b_2(n)\}$의 처음 10개 항은 $\{1, 1, 2, 2, 4, 4, 6, 6, 10, 10\}$이고, $\{b_3(n)\}$의 처음 10개 항은 $\{1, 1, 1, 2, 2, 2, 3, 3, 3, 5\}$이다.

$c_m^k(n)$은 $b_m(n)$의 $k$번째 합성곱으로, 다음과 같이 정의한다.

$c_m^k(n)=\begin{cases} b_m(n), & k = 1 \\ \sum_{i=0}^{n} b_m(i) \cdot c_m^{k-1}(n-i), & k \ge 2 \end{cases}$

보보는 주어진 $n$, $m$, $k$에 대해 다음 값을 구하려 한다.

$f(n) = \left( \sum_{i=0}^{n} c_m^k(i) \right) \bmod (10^9 + 7).$

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($0 \le n \le 10^{18}$, $2 \le m \le 10^{18}$, $1 \le k \le 10$).

$f(n)$의 값을 출력한다.