P4948 Sequence Sum

Given $n, a, k$, compute: $$\sum_{i=1}^n i^k a^i$$ Output the answer modulo $10^9 + 7$.

Input one line with three non-negative integers $n, a, k$. Here $n, a \ge 1$.

Output one line with one integer representing the answer.

| Test Point ID | $n=$ | $k=$ | | :----------: | :----------: | :----------: | | $1$ | $10^6$ | $10^3$ | | $2$ | $10^6$ | $2\times 10^3$ | | $3$ | $10^{18}$ | $0$| | $4$ | $10^{18}$ |$1$ | | $5,6$ | $10^{18}$| $2$ | | $7,8$ | $10^{18}$| $10^3$| | $9,10$ |$10^{18}$ | $2\times 10^3$| For $100\%$ of the testdata, $n \le 10^{18}$, $a \le 10^9$, and $k \le 2000$. Translated by ChatGPT 5