Conditional Game Score Expectation

Alice and Bob are playing a two‐player game. In each round, Alice wins with probability \(p\) and loses with probability \(1-p\) (there is no draw). Initially, both players have 0 points. When a player wins a round, he gains 1 point; when he loses a round, he loses 1 point. However, in this world of game theory, negative numbers are not understood. Therefore, if a player loses a round when his score is \(0\), his score remains \(0\) (while the opponent still gains 1 point).

The game is played for \(N+M\) rounds. Just before Alice was about to ask for the expected value of her final score at the end of the game, the god of this world, temporaryDO, announces an important piece of information: in these \(N+M\) rounds, Alice wins exactly \(N\) rounds!

Under this condition, you need to calculate the mathematical expectation of Alice's final score modulo \(10^9+7\). It is guaranteed 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 the range \([0, 10^9+7)\) such that

[ qx \equiv p \pmod{10^9+7}. ]

Note: Although the game rule mentions that Alice wins with probability \(p\), since it is given that she wins exactly \(N\) rounds, the order of wins and losses among the \(N+M\) rounds is uniformly random among all sequences with exactly \(N\) wins and \(M\) losses.

Analysis:

If we denote Alice's score by \(S\) with \(S_0 = 0\), then for each win we add 1, and for each loss we subtract 1 only if the current score is at least 1; otherwise, the score remains at 0. Observe that an effective loss (which deducts 1 point) only occurs if it happens after at least one win has been achieved. In other words, all losses that occur before the first win are ineffective. Therefore, the final score can be written as:

[ S_{final} = N - (M - L_0), ]

where \(L_0\) is the number of losses that occur before the first win. It is a known combinatorial fact that when \(N\) wins and \(M\) losses are arranged in a random order, the expected number of losses before the first win is \(\frac{M}{N+1}\). Hence, the expected final score is

[ E[S_{final}] = N - M + \frac{M}{N+1} = \frac{N(N+1-M)}{N+1}. ]

Since the answer is a rational number, you should output an integer \(x\in [0, 10^9+7)\) such that

[ x \equiv \frac{N(N+1-M)}{N+1} \pmod{10^9+7}. ]

</p>

You can compute the result modulo \(10^9+7\) using the modular inverse of \(N+1\).

inputFormat

The input consists of a single line containing three values:

• A real number \(p\) representing the probability of winning a round (this value is not used in the calculation due to the condition).
• An integer \(N\) representing the exact number of rounds Alice wins.
• An integer \(M\) representing the number of rounds Alice loses.

These values are separated by spaces.

outputFormat

Output a single integer \(x\) representing the expected final score modulo \(10^9+7\), i.e. the unique solution \(x\) in \([0, 10^9+7)\) such that

\[ (N+1) \cdot x \equiv N(N+1-M) \pmod{10^9+7}. \]

sample

0.5 1 1

500000004