题目背景

题目名称是吸引你点进来的……

我们的出题人CYJian由于出了过多毒瘤题被D死之后，OIer们将他埋葬在地狱十八层之下……

题目描述

已知地狱有$K$个守护者,每个守护者有一个能力值$a_i$。但是我们并不知道他们确切的能力值。只知道这些人的能力值的和为$N$。但是在地狱中守护者的威力会得到加强，具体来说每一个守护者的威力为$a_i^M$。

现在给出$N$,$M$,$K$,请求出所有可能的方案的威力值之和。

输入格式

一行三个整数$N$，$K$和$M$。

输出格式

一行一个整数，表示所有守护者能够发出的可能的威力值之和模$1e9+7$。

5 2 3

100

7 3 1

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个点捆绑测试。