Description

Problem update: Since many people reported difficulty understanding the statement, but to respect the original wording we will not make large changes. You may interpret “minimum” and “maximum” as lower bound and upper bound, similar to the Health in the background.

You now have $m+1$ numbers: the first is $p$, with minimum $0$ and maximum $n$; the remaining $m$ are all infinite, with no minimum or maximum. You may perform any number of rounds. In each round, do the following:

• Uniformly at random choose one number among those that are not at their maximum (if none, do nothing), and add $1$ to it.
• Then perform this step $k$ times: uniformly at random choose one number among those that are not at their minimum (if none, do nothing), and subtract $1$ from it.

What is the expected number of rounds until the first number becomes its minimum $0$.

Input Format

The input contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain four non-negative integers $n$, $p$, $m$, $k$ (as defined above), representing one query.

Output Format

Output $T$ lines, each with one integer, the answer for that query.

If the first number never becomes the minimum $0$ no matter how many rounds, output -1.

Otherwise, it can be proved that the answer is a rational number. Output the answer modulo $10^9+7$, i.e., suppose the answer is $\frac{a}{b}$ (where $a$ and $b$ are coprime positive integers). You must output an integer $x$ such that $0 \le x < 10^9+7$ and $a \equiv b x \pmod{10^9+7}$.

2
2 1 1 1
2 2 1 1

6
8

Hint

Constraints

• For $10\%$ of the testdata, $n \le 3$, $m, k \le 2$.
• For $20\%$ of the testdata, $n, m, k \le 5$.
• For $30\%$ of the testdata, $n, m, k \le 30$.
• For $40\%$ of the testdata, $n, m, k \le 50$.
• For $50\%$ of the testdata, $n, m, k \le 200$.
• For $70\%$ of the testdata, $n \le 200$.
• For $80\%$ of the testdata, $n \le 500$.
• For $100\%$ of the testdata, $1 \le T \le 100$, $1 \le p \le n \le 1500$, $0 \le m, k \le 10^9$.

It is guaranteed that the case $n = p = k = 1$, $m = 0$ does not exist (because the author judged it wrong).

It is guaranteed that the denominator of the answer is not a multiple of $10^9+7$ (because the author did not think of it).

Translated by ChatGPT 5