网格

【题目描述】

左下角是$(0,0)$，右上角是$(W,H)$的网格上，有$(W+1)×(H+1)$个格点。现在要在格点上找$N$个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于$D$。求方案数模$1,000,000,000$。

【输入】

第一行一个整数$T$，表示数据组数。 接下来$T$行，每行四个整数$N,W,H,D$，意义如题目描述。

【输出】

$T$行，每行一个整数表示答案。

【输入样例】

6
2 4 4 1
13 36 48 5
5 5 5 1
50 49 49 1
6 5 5 2
10 55 75 5

【输出样例】

300
2
88
102
0
490260662

【提示】

【数据规模】 对于20%的数据，$N,W,H,D≤10$。 对于50%的数据，$W,H,D≤100$。 另20%的数据，$N≤5$。 对于100%的数据，$N≤50，W,H,D≤500，T≤20$。