Power of Power Partition Function

Let $m$ be a fixed integer with $m \ge 2$. For a positive integer $n$, $b_m(n)$ is the number of ways to write $n$ as a sum of powers of $m$ with non-negative exponents. Repetitions are allowed, and the order of the summands does not matter. We also set $b_m(0) = 1$, since the empty sum is one way.

For example, the first 10 terms of $\{b_2(n)\}$ are $\{1, 1, 2, 2, 4, 4, 6, 6, 10, 10\}$, and the first 10 terms of $\{b_3(n)\}$ are $\{1, 1, 1, 2, 2, 2, 3, 3, 3, 5\}$.

Let $c_m^k(n)$ be the $k$-th convolution power of $b_m(n)$, defined as follows.

$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}$

Given $n$, $m$, and $k$, Bobo wants to find the value of

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

The first line contains three integers $n$, $m$, and $k$ ($0 \le n \le 10^{18}$, $2 \le m \le 10^{18}$, $1 \le k \le 10$).

Print the value of $f(n)$.