【题目描述】
左下角是$(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$。