题目描述

在左下角是 $(0,0)$，右上角是 $(W,H)$ 的网格上，有 $(W+1)\times (H+1)$ 个格点。

现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。

输入格式

第一行一个整数 $T$，表示数据组数。

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

输出格式

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

样例

7
2 2 3 3
1 4 5 3
1 251 497 2
5 40 28 10
2 2 2 2
18 60 58 2
19 2 58 4

9
30
125496
597
16
172006701
0

如图，当 $N=2,W=2,H=3,D=3$ 时，共有 $9$ 种不同的方案。

数据范围

• 对于 $20\%$ 的数据，$N,W,H,D\le 10$。
• 对于 $50\%$ 的数据，$W,H,D\le 100$。
• 对于另 $20\%$ 的数据，$N\le 5$。
• 对于 $100\%$ 的数据，$1\le N\le 50$，$1\le W,H,D\le 500$，$1\le T\le 20$。