시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB42250.000%

문제

Let $m$ be a fixed integer such that $m \ge 2$. For a positive integer $n$, let $b_{m}(n)$ denote the number of ways of writing $n$ as a sum of powers of $m$ using non-negative exponents with repetitions allowed and the order of the summands not being taken into account. We also set $b_{m}(0) = 1$ (there is one empty sum).

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)$, which is defined as follows: $$c_{m}^{k}(n)=\begin{cases} b_{m}(n), & k = 1 \\ \sum\limits_{i=0}^{n} b_{m}(i) \cdot c_{m}^{k-1}(n-i), & k \ge 2 \end{cases}$$

Given $n$, $m$ and $k$, Bobo would like to find the value of $$f(n) = \left( \sum\limits_{i=0}^{n}c^{k}_{m}(i) \right) \bmod (10^9 + 7)\text{.}$$

입력

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

출력

Output an integer denoting the value of $f(n)$.

예제 입력 1

0 2 1

예제 출력 1

1

예제 입력 2

10 2 3

예제 출력 2

2700

예제 입력 3

100 2 10

예제 출력 3

490796617