2912: 后院
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
左下角是(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。