Description

要成为赌神，掷色子当然要相当熟练了。
 
想要成为赌神的Zero碰到了一下难题。
 
有N个色子,每个色子都有K面，值为1~K。
 
现在，将这N个色子排列起来，你可以对任意个色子进行任意的操作（即翻转）。
 
问向上的面的数字和为S的情况有多少种？
 
你想成为赌神吗？那就把这难题解决了吧。

Input

第一行输入一个组数T<=25
 
然后是每组三个整数 N (1 <= N <= 1000), K (1 <= K <= 1000) and S (0 <= S <= 15000).
保证N*S的复杂度不会超时

Output

输出向上面和为S的总数（对 100000007  取模）

Sample Input

5
1 6 3
2 9 8
500 6 1000
800 800 10000
2 100 10

Sample Output

Case 1: 1
Case 2: 7
Case 3: 57286574
Case 4: 72413502
Case 5: 9

HINT

Source

Zero