시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 4 | 2 | 2 | 50.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)$.
0 2 1
1
10 2 3
2700
100 2 10
490796617