题目背景

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

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

题目描述

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

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

输入格式

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

输出格式

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

5 2 3

100

7 3 1

28

提示

• Subtask 1 (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 个点捆绑测试。