Problem:


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



Sample input:
1 25 25 50


Sample output:
2

Submission status: Accepted

Solution code:
n, A, B, c = list(map(int, input().split()))

MOD = 10**9+7
MAX = 200000
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

comb_build(MAX)

ans = 0
a = A*pow(A+B, MOD-2, MOD)%MOD
b = B*pow(A+B, MOD-2, MOD)%MOD
c = 100*pow(100-c, MOD-2, MOD)%MOD

for i in range(n, 2*n):
  t1 = pow(a, n, MOD)%MOD*pow(b, i-n, MOD)%MOD
  t2 = pow(a, i-n, MOD)%MOD*pow(b, n, MOD)%MOD
  ans += nCk(i-1, n-1)*(t1+t2)%MOD*i*c%MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
mod=10**9+7

#factorial,facotiralの逆数を事前計算.
#N=10**5あたりまで有効

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()
    
 
def Combi(N,K):
    return FACT[N]*FACT_INV[N-K]*FACT_INV[K]%mod


ANS=0
SUM=A+B
A_n=pow(A,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
B_n=pow(B,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
SUMINV=pow(SUM,mod-2,mod)

for i in range(N):
    ANS=(ANS+(A_n*pow(B,i,mod)+B_n*pow(A,i,mod))*Combi(N-1+i,i)*pow(SUMINV,i,mod)*(N+i))%mod

print(ANS*100*pow(100-C,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
mod=10**9+7

#factorial,facotiralの逆数を事前計算.
#N=10**5あたりまで有効

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV=FACT_INV[::-1]
    
 
def Combi(N,K):
    return FACT[N]*FACT_INV[N-K]*FACT_INV[K]%mod


ANS=0
SUM=A+B
A_n=pow(A,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
B_n=pow(B,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
SUMINV=pow(SUM,mod-2,mod)

for i in range(N):
    ANS=(ANS+(A_n*pow(B,i,mod)+B_n*pow(A,i,mod))*Combi(N-1+i,i)*pow(SUMINV,i,mod)*(N+i))%mod

print(ANS*100*pow(100-C,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
mod=10**9+7

#factorial,facotiralの逆数を事前計算.
#N=10**5あたりまで有効

FACT=[1,1]
FACT_INV=[1,1]
for i in range(2,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)
    FACT_INV.append(FACT_INV[-1]*pow(i,mod-2,mod)%mod)
    
def Combi(N,K):
    return FACT[N]*FACT_INV[N-K]*FACT_INV[K]%mod


#Aが勝つ場合

ANS=0
SUM=A+B
A_n=pow(A,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
B_n=pow(B,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)%mod
SUMINV=pow(SUM,mod-2,mod)

for i in range(N):
    ANS=(ANS+(A_n*pow(B,i,mod)+B_n*pow(A,i,mod))*Combi(N-1+i,i)*pow(SUMINV,i,mod)*(N+i))%mod

print(ANS*100*pow(100-C,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
mod=10**9+7

#factorial,facotiralの逆数を事前計算.
#N=10**5あたりまで有効

FACT=[1,1]
FACT_INV=[1,1]
for i in range(2,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)
    FACT_INV.append(FACT_INV[-1]*pow(i,mod-2,mod)%mod)
    
def Combi(N,K):
    return FACT[N]*FACT_INV[N-K]*FACT_INV[K]%mod


#Aが勝つ場合

ANS=0
SUM=A+B

for i in range(N):
    ANS=(ANS+(pow(A,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)*Combi(N-1+i,i)*pow(B,i,mod)*pow(pow(SUM,mod-2,mod),i,mod))*(N+i))%mod

#Bが勝つ場合

for i in range(N):
    ANS=(ANS+(pow(B,N,mod)*pow(pow(SUM,mod-2,mod),N,mod)*Combi(N-1+i,i)*pow(A,i,mod)*pow(pow(SUM,mod-2,mod),i,mod))*(N+i))%mod

print(ANS*100*pow(100-C,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def fact(n: int, mod: int):
    ret = [1]
    for i in range(1, n+1):
        ret.append(ret[-1] * i % mod)

    return ret


def fact_inv(fac: list, mod: int):
    ret = []
    for faci in fac:
        ret.append(pow(faci, mod-2, mod))

    return ret


def apb_pow(n: int, a:int, b:int, mod: int):
    ret = [1]
    for i in range(1, 2*n + 1):
        ret.append(ret[-1] * (a+b) % mod)

    return ret


n, a, b, c = li()
MOD = 10**9 + 7
MAXN = 10**5+1

ans = 0

fac = fact(2*MAXN, MOD)
fac_inv = fact_inv(fac, MOD)
apbp = apb_pow(2*MAXN,a,b, MOD)

for m in range(n, 2*n):
    cur = fac[m] * (pow(a, n, MOD) * pow(b, m-n, MOD) + pow(b, n, MOD) * pow(a, m-n, MOD))
    cur %= MOD

    cur *= fac_inv[m-n] * fac_inv[n-1]
    cur %= MOD

    cur *= pow(apbp[m] * (100-c), MOD-2, MOD)
    cur %= MOD

    ans += cur
    ans %= MOD

print(100 * ans % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

def inpl(): return list(map(int, input().split()))
N, A, B, C = inpl()

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

size = 2*100000 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size

g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

P = 0
Q = pow(100-C, 2*N, MOD)*(100-C)%MOD

for x in range(N):
    P = (P + cmb(N+x-1, x, MOD) * (N+x) * pow(100-C, N-x, MOD) * (pow(inverse[A], N-x, MOD) + pow(inverse[B], N-x, MOD)))%MOD
P = P*100*pow(A, N, MOD)*pow(B, N, MOD)%MOD

gcd_ = gcd(P, Q)
P = P//gcd_
Q = Q//gcd_

if A*B == 0:
    print(N*100*pow(100-C, MOD-2, MOD)%MOD)
else:
    print(P*pow(Q, MOD-2, MOD)%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

def inpl(): return list(map(int, input().split()))
N, A, B, C = inpl()

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

size = 2*100000 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size

g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

P = 0
Q = pow(100-C, 2*N, MOD)*(100-C)%MOD

for x in range(N):
    P = (P + cmb(N+x-1, x, MOD) * (N+x) * pow(100-C, N-x, MOD) * (pow(inverse[A], N-x, MOD) + pow(inverse[B], N-x, MOD)))%MOD
P = P*100*pow(A, N, MOD)*pow(B, N, MOD)%MOD

gcd_ = gcd(P, Q)
P = P//gcd_
Q = Q//gcd_

if A*B == 0:
    print(N*100*pow(100-C, MOD-2, MOD)%MOD)
else:
    print(P*pow(Q, MOD-2, MOD)%MOD)

Submission status: Accepted

Solution code:
def c_best_of_2n_minus_1(N, A, B, C, MOD=10**9 + 7):
    class Combination(object):
        """
        組み合わせ
        参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb
        """
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if r == n or r == 0:
                return 1
            if r > n:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    inverse_100 = pow(100, MOD - 2, MOD)
    a = (A * inverse_100) % MOD
    b = (B * inverse_100) % MOD
    c = (C * inverse_100) % MOD

    inverse_a_plus_b = pow(a + b, MOD - 2, MOD)
    a = (a * inverse_a_plus_b) % MOD
    b = (b * inverse_a_plus_b) % MOD

    pow_a = [1]
    pow_b = [1]
    for _ in range(2 * N):
        pow_a.append((pow_a[-1] * a) % MOD)
        pow_b.append((pow_b[-1] * b) % MOD)

    comb = Combination(2 * N, MOD)
    ans = 0
    for m in range(N, 2 * N):
        ans += (comb.combination(m - 1, N - 1)
                * (pow_a[N] * pow_b[m - N] + pow_a[m - N] * pow_b[N])
                * m)
        ans %= MOD
    ans *= pow(1 - c, MOD - 2, MOD)
    return ans % MOD
    # 参考: https://atcoder.jp/contests/m-solutions2019/submissions/5745509

N, A, B, C = [int(i) for i in input().split()]
print(c_best_of_2n_minus_1(N, A, B, C))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = 2 * 10**5 + 10

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

n, a, b, c = [int(item) for item in input().split()]
p = 0; q = 0
for i in range(n):
    p += (pow(a, n, MOD) * pow(b, i, MOD) + pow(a, i, MOD) * pow(b, n, MOD)) * pow(a+b, n-i-1, MOD) * mod_nCr(n+i-1, i) * 100 * (n+i)
    p %= MOD
q = pow(a+b, n*2-1, MOD) * (a + b)
print(p * pow(q, MOD-2, MOD) % MOD)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, A, B, C = map(int, input().split())

    factrial = [1] * (2*N)
    # pa[i] / pab[i] is the probobility that A wins i times when there is no draw.
    pa = [1] * (2*N)
    pb = [1] * (2*N)
    pab = [1] * (2*N)
    for k in range(1, 2*N):
        factrial[k] = (factrial[k-1] * k) % MOD
        pa[k] = (pa[k-1] * A) % MOD
        pb[k] = (pb[k-1] * B) % MOD
        pab[k] = (pab[k-1] * (A+B)) % MOD
    
    fact_inv = [1] * (2*N)
    fact_inv[2*N-1] = pow(factrial[2*N-1], MOD - 2, MOD)
    pab_inv = [1] * (2*N)
    pab_inv[2*N-1] = pow(pab[2*N-1], MOD - 2, MOD)
    for k in range(2*N-2, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD
        pab_inv[k] = (pab_inv[k+1] * (A+B)) % MOD
 
    def comb_mod(n, r, MOD=10**9+7):
        return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    ans = 0
    for m in range(N):
        E = (comb_mod(N+m-1, N-1)\
            * (pa[N]*pb[m] + pa[m]*pb[N]) * pab_inv[N+m]\
            * (N+m) * 100 * pow(100-C, MOD-2, MOD))\
            % MOD

        ans = (ans + E) % MOD

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
MOD = 10**9+7
MAX = 2*10**5
n, a, b, c = map(int, input().split())

fact = [1]*(MAX+1)
pa, pb, pab = [1]*(MAX+1), [1]*(MAX+1), [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%MOD
    pa[i] = (pa[i-1]*a)%MOD
    pb[i] = (pb[i-1]*b)%MOD
    pab[i] = (pab[i-1]*(a+b))%MOD
    
finv = [1]*MAX + [pow(fact[-1], MOD-2, MOD)]
pabinv = [1]*MAX + [pow(pab[-1], MOD-2, MOD)]
for i in range(MAX, 0, -1):
    finv[i-1] = (finv[i]*i)%MOD
    pabinv[i-1] = (pabinv[i]*(a+b))%MOD

def comb(n, r):
    return ((fact[n]*finv[n-r])%MOD*finv[r])%MOD

ans = 0
for m in range(n):
    ans = (ans \
           + comb(n+m-1, n-1)\
           *((pa[n]*pb[m]%MOD + pa[m]*pb[n]%MOD)%MOD)*pabinv[n+m]%MOD\
           *(n+m)%MOD*100%MOD*pow(100-c, MOD-2, MOD)%MOD
           )%MOD

print(ans)

Submission status: Accepted

Solution code:
def inv(x):
    return pow(x, mod - 2, mod)


N, A, B, C = map(int, input().split())
mod = 10 ** 9 + 7
comb = [(1, 1)]
for i in range(N - 1):
    comb.append((comb[i][0] * (N + i) % mod, comb[i][1] * (i + 1) % mod))
comb = [x * inv(y) for x, y in comb]

a = A * inv(A + B) % mod
b = B * inv(A + B) % mod
c = 100 * inv(100 - C)

an = [1, a]
bn = [1, b]
for i in range(N - 1):
    an.append(an[i + 1] * a % mod)
    bn.append(bn[i + 1] * b % mod)
    
ans = 0
for i in range(N):
    t = (i + N) * comb[i] * (an[-1] * bn[i] + bn[-1] * an[i]) % mod
    ans = (ans + t) % mod
ans = ans * c % mod
print(ans)

Submission status: Accepted

Solution code:
import math

N, A, B, C = map(int,input().split())
mod = 10**9+7

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1] 
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

def g(a):
    b, u, v = mod, 1,0
    while b:
        t = a//b
        a -= t * b
        u -= t * v
        a,b,u,v = b,a,v,u
        u %= mod
    return u if u > 0 else u + mod

p1,p2 = A * g(A + B) % mod, B * g(A + B) % mod
p3 = (100 - C) * g(100) % mod

ans = 0
for i in range(N):
    ans += (N+i)*cmb(N+i-1,i,mod)*(pow(p1,N,mod) * pow(p2,i,mod) + pow(p1,i,mod) * pow(p2,N,mod))
    ans %= mod
ans = ans * g(p3) % mod
print(ans)

Submission status: Accepted

Solution code:
import math

N, A, B, C = map(int,input().split())
mod = 10**9+7

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1] 
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

def g(a):
    b, u, v = mod, 1,0
    while b:
        t = a//b
        a -= t * b
        u -= t * v
        a,b,u,v = b,a,v,u
        u %= mod
    return u if u > 0 else u + mod

p1,p2 = A * g(A + B) % mod, B * g(A + B) % mod
p3 = (100 - C) * g(100) % mod

ans = 0
for i in range(N):
    ans += (N+i)*cmb(N+i-1,i,mod)% mod*(pow(p1,N,mod) * pow(p2,i,mod) % mod + pow(p1,i,mod) * pow(p2,N,mod) % mod)% mod
    ans %= mod
ans = ans * g(p3) % mod
print(ans)

Submission status: Accepted

Solution code:
# WARN: Require mod number m is prime number
class ModComb:
    # For nCr mod m
    def __init__(self, n_max, m):
        self._n_max = n_max
        self._m = m
        self._mod_facts = [1] * (n_max+1)       # list of n! mod m
        self._mod_inv_facts = [1] * (n_max+1)   # list of inverse r! mod m

        if not m >= 3:
            raise ValueError('Require mod number m >= 3')

        # Calc n_max! mod m
        for i in range(2, n_max+1):
            self._mod_facts[i] = self._mod_facts[i-1] * i % m

        # Calc inverse r! mod m
        self._mod_inv_facts[n_max] = pow(self._mod_facts[n_max], m-2, m)
        for i in range(n_max-1, 1, -1):
            self._mod_inv_facts[i] = self._mod_inv_facts[i+1] * (i+1) % m

    def calc(self, n, r):
        # Return nCr mod m
        if n > self._n_max:
            raise Exception('n is larger than n_max')

        if r == 0:
            return 1

        m = self._m
        return self._mod_facts[n] * self._mod_inv_facts[r] * self._mod_inv_facts[n-r] % m


# n^p % mod
def modPower(mod, n, p):
    ret = 1
    for i in range(p):
        ret = ret*n % mod
    return ret


# Expected value of the number of all games when M-th non-even game occurs
def expectedGameNum(mod, C, M):
    return M*100*pow(100-C, mod-2, mod) % mod


# Probability of ending game when M-th non-even game occurs
def probEndGame(mod, modcomb, A, B, M, N):
    winA = modcomb.calc(M-1, N-1) * \
            (modPower(mod, A, N) * pow(modPower(mod, 100, N), mod-2, mod) % mod) * \
            (modPower(mod, B, M-N) * pow(modPower(mod, 100, M-N), mod-2, mod) % mod) % mod
    winB = modcomb.calc(M-1, N-1) * \
            (modPower(mod, B, N) * pow(modPower(mod, 100, N), mod-2, mod) % mod) * \
            (modPower(mod, A, M-N) * pow(modPower(mod, 100, M-N), mod-2, mod) % mod) % mod
    return (winA + winB) % mod

def main():
    MOD = 10**9+7
    N, A, B, C = map(int, input().split())
    N_MAX = 100000
    modcomb = ModComb(N_MAX*2, MOD)
    denomi100minusC = pow(100-C, MOD-2, MOD)
    modpowerA = [1] * (N+1)
    for i in range(1, N+1):
        modpowerA[i] = modpowerA[i-1] * A % MOD
    modpowerB = [1] * (N+1)
    for i in range(1, N+1):
        modpowerB[i] = modpowerB[i-1] * B % MOD
    modpower100 = [1] * (N+1)
    for i in range(1, N+1):
        modpower100[i] = modpower100[i-1] * 100 % MOD
    modpowerAB = [1] * (N+1)
    for i in range(1, N+1):
        modpowerAB[i] = modpowerAB[i-1] * (A+B) % MOD
    ans = 0
    for i in range(N, 2*N):
        prob_winA = modcomb.calc(i-1, N-1) * \
                (modpowerA[N] * pow(modpowerAB[N], MOD-2, MOD) % MOD) * \
                (modpowerB[i-N] * pow(modpowerAB[i-N], MOD-2, MOD) % MOD) % MOD
        prob_winB = modcomb.calc(i-1, N-1) * \
                (modpowerB[N] * pow(modpowerAB[N], MOD-2, MOD) % MOD) * \
                (modpowerA[i-N] * pow(modpowerAB[i-N], MOD-2, MOD) % MOD) % MOD
        prob_end_game = (prob_winA + prob_winB) % MOD
        ans += i*100*denomi100minusC % MOD * prob_end_game
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV=10**9+7

def mod_invs(n,mod=DIV):
    inv=[0]*(n+1)
    inv[0]=1
    inv[1]=1
    for i in range(2,n+1):
        inv[i] = (-(mod//i)*inv[mod%i]) % mod
    return inv

N,A,B,C = ints_raw()

def main():
    invs = mod_invs(N*2+100)
    a = A*invs[A+B]%DIV
    b = B*invs[A+B]%DIV
    powas = [1]*(N+1)
    powbs = [1]*(N+1)
    for i in range(N):
        powas[i+1] = powas[i]*a%DIV
        powbs[i+1] = powbs[i]*b%DIV
    inv_perC = 100*invs[100-C]%DIV
    ans = 0
    ncr = 1
    for i in range(N,2*N):
        ncr *= i*invs[i-N]
        ncr %= DIV
        ans += ncr *(powas[N]*powbs[i-N]+powas[i-N]*powbs[N])
        ans %=DIV
    return (ans*inv_perC%DIV)

print(main())

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())

MOD = 10 ** 9 + 7

fact = [0] * (2 * N)
fact[0] = 1

for i in range(1, 2 * N) :
    fact[i] = (fact[i-1] * i) % MOD

def inv(x) :
    return pow(x, MOD - 2, MOD)

def comb(n, r) :
    if n < r or n < 0 or r < 0 :
        return 0
        
    return (fact[n] * inv(fact[n-r]) * inv(fact[r])) % MOD

A_ = A * inv(A+B) % MOD
B_ = B * inv(A+B) % MOD

ret = 0
for M in range(N, 2 * N) :
    ret += (M * comb(M-1, N-1) * pow(A_, N, MOD) * pow(B_, M-N, MOD)) % MOD
    ret += (M * comb(M-1, N-1) * pow(B_, N, MOD) * pow(A_, M-N, MOD)) % MOD
    ret %= MOD
    
ret *= 100 * inv(100 - C) % MOD

print(ret % MOD)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
mod = 10 ** 9 + 7

W = [1] * (2 * N)
for i in range(2 * N - 1):
	W[i + 1] = ((i + 1) * W[i]) % mod

def rev(a):
	return pow(a, mod - 2, mod)

def comb(a, b):
	return (W[a] * rev(W[b]) * rev(W[a - b])) % mod

def f(a, b):
	res = 0
	for i in range(N):
		res += ((i + N) * com[i] * pow(b, i, mod)) % mod
		res %= mod
	return (pow(a, N, mod) * res) % mod

a = A * rev(A + B)
b = B * rev(A + B)
c = C * rev(100)
com = [comb(i + N - 1, i) for i in range(N)]

w_a = f(a, b)
w_b = f(b, a)
ans = ((w_a + w_b) * rev(1 - c)) % mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import Fraction
from operator import add, mul

MOD = 10 ** 9 + 7


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


def mod_add(x, y):
    return add(x, y) % MOD


def cmb(n, r):
    return mod_mul(
        mod_mul(fact[n], inv(fact[r])),
        inv(fact[n - r]))


N, A, B, C = map(int, input().split())

r = mod_mul(100, inv(A + B))
a = mod_mul(A, inv(A + B))
b = mod_mul(B, inv(A + B))

pow_a = [1]
pow_b = [1]
for n in range(N + 1):
    pow_a.append(mod_mul(pow_a[-1], a))
    pow_b.append(mod_mul(pow_b[-1], b))

fact = [1]
for n in range(1, N * 2):
    fact.append(mod_mul(fact[-1], n))

p = 0
for m in range(N, N * 2):
    pa = pow_a[N] * pow_b[m - N]
    pb = pow_a[m - N] * pow_b[N]
    c = cmb(m - 1, N - 1)

    em = mod_mul(mod_mul(mod_mul(c, mod_add(pa, pb)), m), r)
    p = mod_add(p, em)
    # print(m, c, pa, pb, em, p)

f = Fraction(p, 1)
ans = mod_mul(f.numerator, inv(f.denominator))
print(ans)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import time

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

N, A, B, C = mi()

MOD = 10**9+7
a = (A * modinv(A+B, MOD)) % MOD
b = (B * modinv(A+B, MOD)) % MOD
gyakugenofAB = (100 * modinv(A+B, MOD)) % MOD

# 累乗を返すリスト
#[0]行にはaの階乗を、[1]行にはbの階乗を入れる
powlist = [[-1] * (N+1) for _ in range(2)]
preA = 1
preB = 1
powlist[0][0] = 1
powlist[1][0] = 1
for i in range(1,N+1):
  preA = (preA * a) % MOD
  preB = (preB * b) % MOD
  powlist[0][i] = preA
  powlist[1][i] = preB


#cmb(m)でmCn-1を計算
import math
Nmin1fct = modinv(math.factorial(N-1),MOD) % MOD

#一度でも計算したらflagがオン
flag = 0
preans = 1
def cmb(k):
  global flag
  global preans
  ans = 1
  if flag == 0:
    flag = 1
    for i in range(max(1,k-1),k-N,-1):
      ans = (ans * i) % MOD
    preans = (ans * Nmin1fct) % MOD
    return preans
  else:
    preans = (preans * (k-1) * modinv(max(1, k-N),MOD)) % MOD
  return preans
#cmbの計算終わり


#期待値（確率×回数）を足し上げていく。
#N回目～2N-1回目についてループを回す
#m-1Cn-1なことに注意
e = 0
cnt = 0
for m in range(N, 2*N):
#  cnt += 1
#  if cnt % 1000 == 0: print(cnt)
#  start_time = time.perf_counter()
  e += (m * gyakugenofAB * (cmb(m) % MOD) * ((powlist[0][N] * powlist[1][m-N]) + (powlist[0][m-N] * powlist[1][N])))
  e %= MOD
#  print(time.perf_counter() - start_time)


print(e)

Submission status: Accepted

Solution code:
N,A,B,C=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N):
	fact_tmp *= i
	fact_tmp %= mod
	fact.append(fact_tmp)
	inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


P=0
for g in range(N, 2*N):
	P+=pow( A+B , (2*N-1-g) , mod) * g*pow(A,N,mod)* pow(B,g-N,mod) *ncr(g-1,(N-1))
	P%=mod
	P+=pow( A+B , (2*N-1-g) ,mod) * g*pow(A,g-N,mod) * pow(B,N,mod) *ncr(g-1,(N-1))
	P%=mod

Q=pow( A+B , 2*N-1,mod) 

hikiwake=100*pow(100-C,mod-2, mod) 
print ( P*pow(Q, mod-2 , mod) *hikiwake )%mod

Submission status: Accepted

Solution code:
n, a, b, c = [int(i) for i in input().split()]
p = 10 ** 9 + 7

ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(2 * n)
invf = invfact(2 * n, f)

def comb(a, b):
    if a < b:
        return 0
    if a < 0 or b < 0:
        return 0
    return f[a] * invf[b] * invf[a-b] % p

pow_a = [1]
pow_b = [1]
inv_100 = pow(100, p - 2, p)
a = a * inv_100 % p
b = b * inv_100 % p
c = c * inv_100 % p

inv_ab = pow(a + b, p - 2, p)
a = a * inv_ab % p
b = b * inv_ab % p

for i in range(n):
    pow_a.append(pow_a[-1] * a % p)
    pow_b.append(pow_b[-1] * b % p)

for m in range(n, 2 * n):
    ans += comb(m - 1, n - 1) * (pow_a[n] * pow_b[m - n] + pow_a[m - n] * pow_b[n]) * m
    ans %= p

ans *= pow(1 - c, p - 2, p)

print(ans % p)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n, a, b, c = map(int, input().split())
numer, denom = 100, 100 - c
denom *= pow(a+b, 2*n-1, MOD)
x, y = 0, 0
for i in range(n):
	x += (n+i) * comb(n-1+i, i) * pow(b, i, MOD) * pow(a+b, n-1-i, MOD)
	x %= MOD
	y += (n+i) * comb(n-1+i, i) * pow(a, i, MOD) * pow(a+b, n-1-i, MOD)
	y %= MOD
x *= pow(a, n, MOD)
y *= pow(b, n, MOD)
numer *= (x+y) % MOD
ans = numer * pow(denom, MOD-2, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
def Getinv(n):
    inv=[0]*(n+1)
    inv[0]=1
    inv[1]=1
    for i in range(2,n+1):
        inv[i] = (-(Q//i)*inv[Q%i]) % Q
    return inv

Q=10**9+7


def main():
    n,a,b,c=map(int,input().split(' '))
    modinv=Getinv(max(2*n+1,100))
    A=a*modinv[a+b]%Q
    B=b*modinv[a+b]%Q
    powa=[1]*(n+1)
    powb=[1]*(n+1)
    for i in range(n):
        powa[i+1]=powa[i]*A%Q
        powb[i+1]=powb[i]*B%Q
    C=100*modinv[100-c]%Q
    ans = 0
    nowc =1
    for i in range(n,2*n):
        nowc *=i*modinv[i-n]
        nowc %=Q
        ans +=nowc*(powa[n]*powb[i-n]+powa[i-n]*powb[n])
        ans %=Q
    print(ans*C%Q)

main()

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())

mod = 10 ** 9 + 7
table = [1] * (2 * N + 1)
for i in range(2*N):
    table[i+1] = table[i] * (i+1) % mod


def invmod(a, mod=mod):
    # mod が素数の時に成立する
    return pow(a, mod - 2, mod)


def cmb(n, r):
    return (table[n] * invmod(table[r]) * invmod(table[n - r])) % mod


def solve(a, b):
    res = 0
    for i in range(N):
        res += ((i + N) * cmbs[i] * pow(b, i, mod)) % mod
        res %= mod
    return (pow(a, N, mod) * res) % mod


a = A * invmod(A + B, mod)
b = B * invmod(A + B, mod)
c = C * invmod(100, mod)
cmbs = [cmb(i + N - 1, i) for i in range(N)]

Ea = solve(a, b)
Eb = solve(b, a)
ans = ((Ea + Eb) * invmod(1 - c, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b, c = [int(i) for i in input().split()]
p = 10 ** 9 + 7

ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(2 * n)
invf = invfact(2 * n, f)

def comb(a, b):
    if a < b:
        return 0
    if a < 0 or b < 0:
        return 0
    return f[a] * invf[b] * invf[a-b] % p

pow_a = [1]
pow_b = [1]
inv_100 = pow(100, p - 2, p)
a = a * inv_100 % p
b = b * inv_100 % p
c = c * inv_100 % p

ab = pow(a + b, p - 2, p)
a = (a + a * ab * c) % p
b = (b + b * ab * c) % p

for i in range(n):
    pow_a.append(pow_a[-1] * a % p)
    pow_b.append(pow_b[-1] * b % p)

for m in range(n, 2 * n):
    ans += comb(m - 1, n - 1) * (pow_a[n] * pow_b[m - n] + pow_a[m - n] * pow_b[n]) * m
    ans %= p

ans *= pow(1 - c, p - 2, p)

print(ans % p)

Submission status: Accepted

Solution code:
div=10**9+7
def modinv(a, m=1000000007): return pow(a, m-2, m)

N,A,B,C=list(map(int,input().split()))
fact=[1]*(2*N+1)
res = 0
invAB = modinv(A+B)
reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

for i in range(1, 2*N+1): fact[i] = fact[i-1]*i % div
def ncr(n, r): return fact[n]*modinv(fact[r]*fact[n-r]%div) % div

for i in range(1, N+1): 
    memoA[i] = (memoA[i-1]*A*invAB) % div
    memoB[i] = (memoB[i-1]*B*invAB) % div

for i in range(N, 2*N): res += (((ncr(i-1, N-1)*memoA[N] % div)*memoB[i-N] + (ncr(i-1, N-1)*memoB[N] % div)*memoA[i-N]) % div)*reveven*i % div

print(res % div)

Submission status: Accepted

Solution code:
# 入力
N, A, B, C = map(int, input().split())

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# f[n] = n! % (10**9 + 7)
f = [0 for _ in range(2 * N)]
f[0] = ModInt(1)
for i in range(1, 2 * N):
    f[i] = i * f[i - 1]

# 引き分けなしの分母
D = ModInt(100 - C)
# 1回のゲームにつき、高橋君が勝つ確率
p = A / D
# 1回のゲームにつき、青木君が勝つ確率
q = B / D

# 高橋君がN回、青木君がi回勝つケースの重み付き期待値の和、および
# 高橋君がi回、青木君がN回勝つケースの重み付き期待値の和
# を求めそれらの和を解とする
ans = (100 / D) * sum(
    (N + i) * (f[N + i - 1] / (f[i] * f[N - 1])) * (p**N * q**i + p**i * q**N)
    for i in range(N)
)

# 出力
print(ans)