题目描述

左下角是$(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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。