题目描述
Problem Description
Given \( n, a, k \), compute the following sum:
\[ \sum_{i=1}^n i^k a^i \]
The answer should be taken modulo \( 10^9 + 7 \).
Input Format
A single line containing three positive integers \( n, a, k \).
Output Format
A single line containing one integer representing the answer.
Sample Input and Output
Sample Input #1
3 4 0
Sample Output #1
84
Sample Input #2
3 10 1
Sample Output #2
3210
Sample Input #3
3 9 2
Sample Output #3
6894
Notes
| Test Case Number | \( 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 data, \( n \leq 10^{18} \), \( a \leq 10^9 \), \( k \leq 2000 \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分
样例输入
3 4 0
样例输出
84