3684: 方格计数(第二轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
在左下角是 (0, 0)，右上角是 (W, H)的网格上，有 (W + 1) × (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提示
【样例 1 说明】
如图，当 N = 2, W = 2, H = 3, D = 3时，共有 9 种不同的方案。
【数据范围】
对于 20% 的数据， N, W, H, D ≤ 10 。
对于 50% 的数据， N, W, H, D ≤ 100。
对于另 20% 的数据， N ≤ 5。
对于 100% 的数据， 1 ≤ N ≤ 50， 1 ≤ W, H, D ≤ 500， 1 ≤ T ≤ 20。