Description

Alice and Bob are playing a two-player game. In each round, Alice wins with probability $p$ and loses with probability $1-p$, and no tie occurs.

Both players start with $0$ points. When a player wins, they gain $1$ point; when a player loses, they lose $1$ point. Unfortunately, people in the world of game theory cannot comprehend negative numbers. Therefore, if someone loses a round while they have $0$ points, they will not be deducted any points (the opponent still gains $1$ point as usual). The game consists of $N+M$ rounds in total. Alice asks you to compute the expected value of her score at the end of the game.

“This is nothing. I, little L, can do it in a minute!” You, being even more skilled than little L, also get the answer easily. But just as you are about to tell Alice the answer, the god of the game theory world—temporaryDO—appears and brings an important piece of information: among these $N+M$ rounds, Alice wins exactly $N$ rounds!

Being familiar with conditional probability, you immediately realize that you need to adjust your computation to obtain the correct answer.

To avoid precision issues, please output the result modulo $10^9+7$. That is, our testdata guarantees that the answer is a rational number $\frac{p}{q}$ with $10^9+7 \nmid q$. You only need to find an integer $x \in [0, 10^9+7)$ such that $q x \equiv p \pmod{10^9+7}$.

Input Format

The first line contains two positive integers $T$, $P'$, where $T$ is the number of test cases, and $\frac{P'}{1000}$ equals $p$, i.e., Alice’s probability of winning each round.

Then follow $T$ lines. Each line contains two nonnegative integers $N, M$, representing one test case.

Output Format

Output $T$ lines, each containing one integer, which is the answer for the corresponding test case.

3 500
1 1
2 3
4 4

500000004
200000002
728571435

Hint

In each round, Alice has probability $\frac{1}{2}$ to win.

• For the first test case, Alice’s win may occur in the first or second round, with equal probability. If she wins in the first round, her final score is $0$; otherwise, her score is $1$. Hence the expectation is $\frac{1}{2}$. Verification: $2 \times 500000004 \equiv 1 \pmod{10^9+7}$.
• For the second test case, the expected value is $\frac{3}{5}$.
• For the third test case, the expected value is $\frac{93}{70}$.

Constraints and Conventions

1. For 10% of the testdata, $N, M, T \le 50$.
2. For an additional 20% of the testdata, $N, M, T \le 2000$.
3. For an additional 20% of the testdata, $N, M \le 10^5$, $|N-M| \le 200$, $T \le 2 \times 10^5$.
4. For an additional 20% of the testdata, $N, M, T \le 5 \times 10^4$.
5. For 100% of the testdata, $N+M, T \le 2.5 \times 10^5$, $0 < P' < 1000$.

Credit: https://www.luogu.org/discuss/show?postid=35727

Translated by ChatGPT 5