数列求和
题目描述
给定 $n,a,k$，求：
$$\sum_{i=1}^n i^k a^i$$
答案对 $10^9 + 7$ 取模。
输入输出格式
输入格式
输入一行三个正整数 $n,a,k$。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入样例 #1
3 4 0输出样例 #1
84输入样例 #2
3 10 1输出样例 #2
3210输入样例 #3
3 9 2输出样例 #3
6894说明
| 测试点编号 | $n=$ | $k=$ |
| :----------: | :----------: | :----------: |
| $1$ | $10^6$ | $10^3$ |
| $2$ | $10^6$ | $2*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*10^3$|
对于 $100\%$ 的数据，$n\le10^{18}$，$a\le10^9$，$k\le2000$