数列求和

题目描述

求数列 ${b_n \ = \ n^ka^n}$ 的前 ${n}$ 项和 ${T_n \ mod \ \left( 10^9+7 \right) }$

输入输出格式

输入格式


输入共 1 行,包含 3 个非负整数: n,a,k

输出格式


输出共 1 行,包含 1 个非负整数:${T_n \ mod \ \left( 10^9+7 \right) }$

输入输出样例

输入样例 #1

3 4 0

输出样例 #1

84

输入样例 #2

3 10 1

输出样例 #2

3210

输入样例 #3

3 9 2

输出样例 #3

6894

说明

![Luogu](https://cdn.luogu.org/upload/pic/37937.png)