Description

题目更新：鉴于很多人反映看不懂题，但是出于尊重原题面的原则不进行大幅度更改。您可以将最小值和最大值理解为下限和上限，类似于题目背景中的血量。

你现在有 $m+1$ 个数：第一个为 $p$，最小值为 $0$，最大值为 $n$；剩下 $m$个都是无穷，没有最小值或最大值。你可以进行任意多轮操作，每轮操作如下：

在不为最大值的数中等概率随机选择一个（如果没有则不操作），把它加一；

进行 $k$次这个步骤：在不为最小值的数中等概率随机选择一个（如果没有则不操作），把它减一。

现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。

Input Format

输入包含多组数据。 输入第一行包含一个正整数 $T$，表示数据组数。 接下来 $T$行 ，每行 4个非负整数 $n$、$p$、$m$、$k$（含义见题目描述），表示一次询问。

Output Format

输出 $T$行，每行一个整数，表示一次询问的答案。

如果无论进行多少轮操作，第一个数都不会变为最小值 $0$，那么输出-1；

否则，可以证明答案一定为有理数，那么请输出答案模 $10^9+7$ 的余数，即设答案为 $\frac{a}{b}$（$a$、$b$为互质的正整数 ），你输出的整数为 $x$，那么你需要保证 $0 \leq x < 10^9+7$ 且 $a \equiv bx (\mod 10^9+7)$。

2
2 1 1 1
2 2 1 1

6
8

Hint

###数据范围

对于 $10\%$ 的数据， $n \leq 3$ ，$m, k \leq 2$ 。

对于 $20\%$ 的数据， $n, m, k \leq 5$ 。

对于 $30\%$ 的数据， $n, m, k \leq 30$ 。

对于 $40\%$ 的数据， $n, m, k \leq 50$ 。

对于 $50\%$ 的数据， $n, m, k \leq 200$ 。

对于 $70\%$ 的数据， $n \leq 200$ 。

对于 $80\%$ 的数据， $n \leq 500$ 。

对于 $100\%$ 的数据， $1 \leq T \leq 100$，$1 \leq p \leq n \leq 1500$ ，$0 \leq m, k \leq 10^9$。

保证不存在 $n=p=k=1$, $m=0$ 的情况（因为出题人判错了）

保证不存在答案的分母是 $10^9+7$ 的倍数的情况（因为出题人没想到）