Background

(Players who have not played Hearthstone can skip this paragraph.) Today we discuss the interaction between “Healing Rain” (restore $12$ Health, randomly distributed among all friendly characters) and “Shadowstrike Armor” (whenever a character is healed, deal $1$ damage to a random enemy). Suppose you have $m$ minions on your side with infinite remaining Health and infinite missing Health (i.e., no upper or lower bounds), and your opponent has $k$ copies of Shadowstrike Armor on the board. Your hero has current Health $p$ and maximum Health $n$. Now you cast a Healing Rain that can restore infinitely many Health (instead of $12$). What is the expected total amount of Health restored by Healing Rain before your hero dies (Health drops to $0$; due to Healing Rain’s targeting rules, the hero will no longer be healed afterward).

Note: If the background conflicts with the problem statement, follow the problem statement.

Below is the formal description of the problem.

Problem 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