Problem C: We all love stones

Problem C: We all love stones

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit][Status][Web Board]

Description

Aseer和DFS叒在一起玩游戏了。有N(1≤N≤10000)个格子和K(1≤K≤100)个石子,其中一半石子是黑色,一半是白色。最左边是白色石头,最右边是黑色石头,相邻石头颜色不同。Aseer可以移动白色石子,DFS可以移动黑色棋子,每次可以同时移动至多d(d≤k)个石子,石子不能越过这N个格子,也不能跨越它两边的石子。Aseer和DFS轮流操作,Aseer先操作。先不能操作者失败。

Aseer想知道,已知N和K,且两个人都足够聪明,有多少种初始石子的布局可以让她有必胜策略。

但Aseer并不擅长博弈,她找到了聪明的你,希望你能帮他解决问题。

Input

第一行包含一个数T,表示有T组数据。(T≤100)

每组数据包含一行,包含三个数字N, K, D。

Output

对于每组数据,输出Aseer能胜利的方案数。对1000000007取模。

Sample Input

1
10 8 2

Sample Output

30

HINT

[Submit][Status]