Statement
在火星第一城有 N 个公交车站，它们都排成一条长度为 N-1 km 的直线。市长喜欢把事情保持简单，所以他给公交车站编号为 1 到 N，相邻车站之间恰好相隔 1 km。
城市中还有 K 辆公交车。市长需要规划公交时刻表，他想知道有多少种方式可以完成。这个数可能非常大。幸运的是，有一些限制条件：
- 每天开始时，所有公交车都在前 K 个公交站（每个站一辆公交车）
- 公交车只能从左向右移动（1 是最左边的公交站）
- 每天结束时，所有公交车必须位于最后 K 个公交站（每个站一辆公交车）
- 每个公交车站必须恰好停靠一辆公交车
- 对于同一辆公交车，任意两个连续停靠站之间的距离至多为 P km
帮助市长计算时刻表数量。不过尽量不要给他带来非常糟糕的消息（大量时刻表），所以只需输出真实数量对 30031 取模后的结果。
Input
输入文件的第一行是数据组数 T。
接下来的 T 行每行包含 3 个用单个空格分隔的整数：
N、K 和 P。
### 数据范围
- 1 < T ≤ 30
- 1 < P ≤ 10
- K < N
- 1 < K ≤ P
- 1 < N < 1000
- 1 < N < 10
Output
对于每组数据，按测试用例顺序逐个输出规划公交时刻表的方式数（对 30031 取模），格式为 "[number of ways modulo 30031]"。
Examples
Input
3
10 3 3
5 2 3
40 4 8Output
1
3
7380Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: dynamic-programming
- Tag: math