毒瘤之神异之旅
题目背景
题目名称是吸引你点进来的……
我们的出题人CYJian由于出了过多毒瘤题被D死之后,OIer们将他埋葬在地狱十八层之下……
题目描述
已知地狱有$K$个守护者,每个守护者有一个能力值$a_i$。但是我们并不知道他们确切的能力值。只知道这些人的能力值的和为$N$。但是在地狱中守护者的威力会得到加强,具体来说每一个守护者的威力为$a_i^M$。
现在给出$N$,$M$,$K$,请求出所有可能的方案的威力值之和。
输入输出格式
输入格式
一行三个整数$N$,$K$和$M$。
输出格式
一行一个整数,表示所有守护者能够发出的可能的威力值之和模$1e9+7$。
输入输出样例
输入样例 #1
5 2 3
输出样例 #1
100
输入样例 #2
7 3 1
输出样例 #2
28
说明
Subtask1(20 pts):
$1 \leq N,M \leq 10$
$1 \leq K \leq N$
Subtask 2(40 pts):
$1 \leq N,M \leq 4096$
$1 \leq K \leq N$
Subtask 3(40 pts):
$1 \leq N,M \leq 10000$
$1 \leq K \leq N$
其中所有的$a_i$均需要是正整数.
不要喷出题人毒瘤卡常,每一档部分分的时间和空间都至少开了标程的两倍。
由于数据只有一组,可能强度较弱,所以需要每5个点捆绑测试。