Description

这天$AKK$组织同学们一起玩起了骰子小游戏，骰子游戏的规则是这样的，每个同学分别掷出$n$个骰子，如果某个同学当前骰子向上的面的数字之和等于$s$则记1分，当然这里用的骰子和一般的骰子是不一样的，每个骰子有$f$个面，这些面的值分别是$1,2,3,..,f$。$BKK$同学很快注意到和为$s$的情况有若干种，但是他卖了个关子，现在请你计算一个一共有多少种情况。注意由于最终答案可能很大，你需要对1000000007取模。

Format

Input

一行,共三个数，分别表示$n,f,s$

Output

一行，一个数，表示和为$s$的方案数

Samples

1 6 3

1

2 6 7

6

30 30 500

222616187

Limitation

1s, 1024KiB for each test case.

Tips

样例说明

样例$1$只有$3$这一种情况 样例$2$所有可能有$6+1,5+2,4+3,3+4,2+5,1+6$ 共6种可能 样例$3$是对$1000000007$取模后的结果

数据范围

$1 \leq n,f \leq 30$ $1 \leq s \leq 1000$