数列求和

题目描述

给定 $n,a,k$,求: $$\sum_{i=1}^n i^k a^i$$ 答案对 $10^9 + 7$ 取模。

输入输出格式

输入格式


输入一行三个非负整数 $n,a,k$。其中 $n, a \ge 1$。

输出格式


输出一行一个整数表示答案。

输入输出样例

输入样例 #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\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$| 对于 $100\%$ 的数据,$n\le10^{18}$,$a\le10^9$,$k\le2000$