题目描述

这里我们有$n$个一模一样的骰子（只是排除其他无效信息）骰子颜色不同，每一个骰子上面都有$k$个面，分别是$1$到$k$。

给定三个整数$n, k, target$，请输出投掷骰子使得骰子面朝上的数字总和等于$target$可能得到的所有情况方案数。

所以我们每次选择时候不同骰子是独立的。

由于答案很大，你需要对$10^{9} + 7$取模。

样例输入

第一行三个整数分别是$n, k, target$。

样例输出

输出一个整数作为答案。

样例

样例一

1 6 3

1

样例解释：你投掷了一个只有$6$个面的骰子，得到总和为$3$的只有一种i情况。

样例二

2 6 7

6

样例解释：你投掷了两个骰子，每个骰子$6$个面，有$6$种方式得到总和为$7$的情况：$1 + 6, 2 + 5, 3 + 4, 4 + 3, 5 + 2, 6 + 1$。

数据范围

$1 \le n, k \le 30$

$1 \le target \le 10^{3}$