C - Best-of-(2n-1)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

高橋君と青木君がゲームをします。 どちらかが合計で N 回勝つまでゲームを繰り返し行います。

1 回ゲームを行ったとき、高橋君が勝つ確率は A %、青木君が勝つ確率は B %、 どちらも勝たず引き分けとなる確率は C %です。 ゲームが行われる回数の期待値を求めて、以下のように出力してください。

求める期待値は互いに素な整数 P, Q を用いて P/Q と表せます。 R \times Q \equiv P\pmod {10^9+7} となる 0 以上 10^9+6 以下の整数 R を出力してください。 (この問題の制約下で、このような R は必ず一意に存在します。)

制約

  • 1 \leq N \leq 100000
  • 0 \leq A,B,C \leq 100
  • 1 \leq A+B
  • A+B+C=100
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N A B C

出力

ゲームが行われる回数の期待値を問題文で指定した方法にしたがって出力せよ。


入力例 1

1 25 25 50

出力例 1

2

N=1 なのでゲームはどちらかが勝つまで繰り返されます。 期待値は 2 となります。


入力例 2

4 50 50 0

出力例 2

312500008

C=0 となることがあります。


入力例 3

1 100 0 0

出力例 3

1

B=0 となることもあります。


入力例 4

100000 31 41 28

出力例 4

104136146

Score : 500 points

Problem Statement

Takahashi and Aoki will play a game. They will repeatedly play it until one of them have N wins in total.

When they play the game once, Takahashi wins with probability A %, Aoki wins with probability B %, and the game ends in a draw (that is, nobody wins) with probability C %. Find the expected number of games that will be played, and print it as follows.

We can represent the expected value as P/Q with coprime integers P and Q. Print the integer R between 0 and 10^9+6 (inclusive) such that R \times Q \equiv P\pmod {10^9+7}. (Such an integer R always uniquely exists under the constraints of this problem.)

Constraints

  • 1 \leq N \leq 100000
  • 0 \leq A,B,C \leq 100
  • 1 \leq A+B
  • A+B+C=100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B C

Output

Print the expected number of games that will be played, in the manner specified in the statement.


Sample Input 1

1 25 25 50

Sample Output 1

2

Since N=1, they will repeat the game until one of them wins. The expected number of games played is 2.


Sample Input 2

4 50 50 0

Sample Output 2

312500008

C may be 0.


Sample Input 3

1 100 0 0

Sample Output 3

1

B may also be 0.


Sample Input 4

100000 31 41 28

Sample Output 4

104136146