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:
#Combinationクラス
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD



from fractions import Fraction


MOD = 10**9 + 7
n, a, b, c = map(int, input().split())

#n-1から2n-2まで
comb = Combination(2*n, MOD)
mod_li = [1]
for i in range(1, 2*n + 1):
    mod_li.append(mod_li[-1] * (a+b) % MOD)
p1 = [1]
p2 = [1]
for i in range(1, n+1):
    p1.append((p1[-1] * a) % MOD)
    p2.append((p2[-1] * b) % MOD)
q = mod_li[2*n-1]
p = 0


for i in range(n):
    tmp_bunshi = (n+i) * (mod_li[n-i-1]) * p1[n] * p2[i] * comb.combination(n-1+i,i)
    tmp_bunshi += (n+i) * (mod_li[n-i-1]) * p2[n] * p1[i] * comb.combination(n-1+i,i)
    p += tmp_bunshi
    p %= MOD
p *= 100
q *= (a+b)
ans = Fraction(p, q)
p = ans.numerator
q = ans.denominator
print((pow(q, MOD-2, MOD) * p) % MOD)

Submission status: Accepted

Solution code:
import math
import fractions
mod = 10 ** 9 + 7

nmax = 2 * 10 ** 5 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


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


G = fractions.gcd(A, B)
A = int(A / G)
B = int(B / G)

P = 0
A_N = pow(A, N, mod)
B_N = pow(B, N, mod)
for i in range(N):
    P = (P + ((N + i) * ((((A_N * pow(B, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod
                        + (((B_N * pow(A, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod)) % mod) % mod
P = (P * 100) % mod
Q = (pow(A+B, 2*N-1, mod) * (100 - C)) % mod
print((P * pow(Q, mod-2, mod)) % mod)

Submission status: Accepted

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

W = [1] * (2 * N + 1)
for w in range(2 * N):
    W[w + 1] = ((w + 1) * W[w]) % 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:
MOD = 10**9 + 7
N,A,B,C = map(int,input().split(' '))

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

INV = [0] * 101
INV[1] = 1
for i in range(2,101):
	INV[i] = (INV[MOD % i] * (MOD - MOD//i) % MOD)

ap = [1] * (N+1)
bp = [1] * (N+1)
for i in range(1,N+1):
	ap[i] = ap[i-1] * A % MOD
	bp[i] = bp[i-1] * B % MOD

icp = [1] * (2*N+1)
for i in range(1,2*N+1):
	icp[i] = icp[i-1] * INV[100-C] % MOD

a = [0] * (2*N)

j = 1
a[N] =(ap[N] + bp[N]) % MOD
for i in range(N+1,2*N):
	f = fact[i-1] * ifact[j] * ifact[i-1-j] % MOD
	a[i] = fact[i-1] * ifact[j] * ifact[i-1-j] % MOD
	a[i] *= (ap[N] * bp[j] + ap[j] * bp[N]) % MOD
	j = j + 1

p = [0] * (2*N)
for i in range(N,2*N):
	p[i] = a[i] * i * icp[i+1] % MOD

print(sum(p)*100 % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def reduce(y, x):
    tmp = gcd(x, y)
    return (y // tmp, x // tmp)

def get_z(y, x): # y/x (mod 1000000007)
    inv_x = pow(x, MOD - 2, MOD)
    return y * inv_x % MOD

def make_combs(n, k):
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    ret = [0] * (n + 1)
    for i in range(k, n + 1):
        a = fact[i]
        b = (fact[k] * fact[i - k]) % MOD
        ret[i] = get_z(a, b)
    return ret


def make_pow(y, x, n):
    ret = [0] * (n + 1)
    yy = [1] * (n + 1)
    xx = [1] * (n + 1)
    for i in range(1, n + 1):
        yy[i] = ((yy[i - 1] * y) % MOD)
        xx[i] = ((xx[i - 1] * x) % MOD)
    for i in range(n + 1):
        #print(yy[i], xx[i])
        ret[i] = get_z(yy[i], xx[i])
    return ret

def solve(n: int, A: int, B: int, C: int):
    y = 0
    x = 0
    AB = 100 - C
    combs = make_combs(2 * n, n - 1)
    a, a_ab = reduce(A, AB)
    b, b_ab = reduce(B, AB)
    a_pow = make_pow(a, a_ab, n)
    b_pow = make_pow(b, b_ab, n)
    #print(combs)
    #print(a_pow)
    #print(b_pow)
    for i in range(n, n * 2):
        com = combs[i - 1]
        #tmp  = (A / ab) ** (n) + (B / ab) ** (i - n)
        #tmp += (B / ab) ** (n) + (A / ab) ** (i - n)
        tmp  = a_pow[n] * b_pow[i - n]
        tmp += b_pow[n] * a_pow[i - n]
        #print(a_pow[n], b_pow[i - n], b_pow[n], a_pow[i - n])
        x = (x + tmp * com) % MOD
        y = (y + tmp * com * i) % MOD
    x = (x * (100 - C)) % MOD
    y = (y * 100) % MOD
    ret = get_z(y, x)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    solve(N, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10**9+7

def inv(n):
    n %= mod
    return pow(n,mod-2,mod)

fact = [1]*(N+1)

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

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

d = [0]*(2*N+1)

d[0] = inv(1-c)
for i in range(2*N):
    d[i+1] = (i+1)*inv(1-c)*d[i]%mod

ans = 0
for k in range(N):
    ans += (pow(a,N,mod)*pow(b,k,mod)+pow(a,k,mod)*pow(b,N,mod))%mod*inv(fact[N-1])*inv(fact[k])%mod*d[N+k]%mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

SIZE=200000; MOD=10**9+7 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

n,pa,pb,pc = [int(i) for i in input().split()]

ans = 0
for b in range(n):
    ans += (n+b)*(pow(100,n+b,MOD)*pow(inv[100-pc],n+b,MOD))%MOD *pow(pa,n,MOD)%MOD *pow(pb,b,MOD)%MOD *choose(n-1+b,b)%MOD * inv[pb+pa]%MOD * pow(inv[100],n-1+b,MOD)%MOD
    ans %= MOD
    

for b in range(n):
    ans += (n+b)*(pow(100,n+b,MOD)*pow(inv[100-pc],n+b,MOD))%MOD *pow(pa,b,MOD)%MOD *pow(pb,n,MOD)%MOD *choose(n-1+b,b)%MOD * inv[pb+pa]%MOD * pow(inv[100],n-1+b,MOD)%MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:

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

LARGE = 10 ** 9 + 7


def p_inv(a):
    return pow(a, LARGE - 2, LARGE)


# not C 1 time
S = p_inv((1 - C * p_inv(100)) % LARGE)
#S = S * S % LARGE

# A / B
p = A * p_inv(A + B) % LARGE
q = B * p_inv(A + B) % LARGE

ncr_A_list = [0]*N
p0 = pow(p, N - 1, LARGE)
ncr_A_list[0] = p0
for i in range(1, N):
    p0 = (p0 * q * (N - 1 + i) * p_inv(i)) % LARGE
    ncr_A_list[i] = p0

ncr_B_list = [0]*N
q0 = pow(q, N - 1, LARGE)
ncr_B_list[0] = q0
for i in range(1, N):
    q0 = (q0 * p * (N - 1 + i) * p_inv(i)) % LARGE
    ncr_B_list[i] = q0

inv_C_list = [0]*N
r00 = ((A + B) * p_inv(100)) % LARGE
r0 = pow(r00, N, LARGE)
inv_C_list[0] = r0
for i in range(1, N):
    r0 = (r0 * r00) % LARGE
    inv_C_list[i] = r0

res = 0
#for i in range(N):
#    res += (((ncr_A_list[i] * p * inv_C_list[i]) % LARGE) * ((S * (N + i)) % LARGE)) % LARGE
#    res += (((ncr_B_list[i] * q * inv_C_list[i]) % LARGE) * ((S * (N + i)) % LARGE)) % LARGE
#    res = res % LARGE

for i in range(N):
    res += (((ncr_A_list[i] * p) % LARGE) * ((S * (N + i)) % LARGE)) % LARGE
    res += (((ncr_B_list[i] * q) % LARGE) * ((S * (N + i)) % LARGE)) % LARGE
    res = res % LARGE


print(res)

Submission status: Accepted

Solution code:

MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    A = int(buflist[1])
    B = int(buflist[2])
    C = int(buflist[3])
    # ABの二項分布*1-Cの逆数っぽい
    # nCnから(2n-1)Cnまで計算
    divisor = 1
    for i in range(1, N+1):
        divisor = (divisor * i) % MOD
    nCr = []
    dividend = divisor
    for i in range(1, N+1):
        nCr.append((dividend * modinv(divisor)) % MOD)
        dividend = (dividend * (i+N)) % MOD
        dividend = (dividend * modinv(i)) % MOD
    Apow = []
    Bpow = []
    pow100 = []
    a = 1
    b = 1
    p100 = 1
    for i in range(N+1):
        Apow.append(a)
        Bpow.append(b)
        pow100.append(p100)
        a = (a * A) % MOD
        b = (b * B) % MOD
        p100 = (p100 * (A + B)) % MOD
    probability = []
    for i in range(N, 2*N):
        dividend = 1
        divisor = 1
        dividend = (dividend * nCr[i-N]) % MOD
        dividend = (dividend * Apow[N]) % MOD
        dividend = (dividend * Bpow[i-N]) % MOD
        divisor = (divisor * pow100[N]) % MOD
        divisor = (divisor * pow100[i-N]) % MOD
        probability.append(((dividend * 100) % MOD, (divisor * (100-C)) % MOD))
    for i in range(N, 2*N):
        dividend = 1
        divisor = 1
        dividend = (dividend * nCr[i-N]) % MOD
        dividend = (dividend * Bpow[N]) % MOD
        dividend = (dividend * Apow[i-N]) % MOD
        divisor = (divisor * pow100[N]) % MOD
        divisor = (divisor * pow100[i-N]) % MOD
        probability.append(((dividend * 100) % MOD, (divisor * (100-C)) % MOD))
    dividend = probability[0][0]
    divisor = probability[0][1]
    for i in range(1, len(probability)):
        dividend = (dividend * probability[i][1]) % MOD
        dividend = (dividend + (probability[i][0] * divisor) % MOD) % MOD
        divisor = (divisor * probability[i][1]) % MOD
    print((dividend * modinv(divisor) * N) % MOD)

def modinv(x, m = MOD):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import sys
range = xrange
input = raw_input

mod = 10**9+7
MOD = 10**9+7

big = 10**6
modinv = [1]*big
for i in range(2,big):
    modinv[i] = (-(MOD//i)*modinv[MOD%i])%MOD

fac = [1]
for i in range(1,big):
    fac.append(fac[-1]*i%MOD)

invfac = [1]
for i in range(1,big):
    invfac.append(invfac[-1]*modinv[i]%MOD)

def choose(n,k):
    return fac[n]*invfac[k]%MOD*invfac[n-k]%MOD


modinv = lambda x: pow(x,mod-2,mod)

n,a,b,c = [int(x) for x in input().split()]

a *= modinv(100)
b *= modinv(100)
c *= modinv(100)




#def nck(n,k):
#    prod = 1
#    for i in range(1,n+1):
#        prod *= i
#    for i in range(1,k+1):
#        prod //= i
#    for i in range(1,n-k+1):
#        prod //= i
#    return prod

fa = a*modinv(a+b)%MOD
fb = b*modinv(a+b)%MOD

fapow = [1]
for _ in range(100010):
    fapow.append(fapow[-1]*fa%MOD)

fbpow = [1]
for _ in range(100010):
    fbpow.append(fbpow[-1]*fb%MOD)


def dp2(x,y):
    if x==n:
        return fa * dp2(x-1,y)
    elif y==n:
        return fb * dp2(x,y-1)
    elif x == n-1 or y == n-1:
        return choose(x+y,y) * fapow[x] % MOD*fbpow[y]


s = 0
for i in range(n):
    k = (n+i)*modinv(1-c)%MOD
    s = (s + k*dp2(n,i))%MOD
    s = (s + k*dp2(i,n))%MOD
print s
#for i in range(100):
#    A = []
#    for j in range(10):
#        x = dp(i,j)
#        denom = 1
#        while x%1:
#            x *= 2
#            denom *= 2
#        A.append((x,denom))
#    print [A]

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b,c=map(int,input().split())
m=2*10**5
def modinv(n):
    return pow(n,mod-2,mod)
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
p=a*modinv(100-c); q=b*modinv(100-c)
ans=0
for k in range(n,2*n):
    ans+=k*comb(k-1,n-1)*(pow(p,n,mod)*pow(q,k-n,mod)+pow(p,k-n,mod)*pow(q,n,mod))
    ans%=mod
ans*=100*modinv(100-c)
print(ans%mod)

Submission status: Accepted

Solution code:
# 約分無視できる！！
# A+B/100で勝負がつくので、最後に100/A+Bをかける
MOD = 10**9 + 7

def inv_mod(a):
  return pow(a,MOD-2,MOD)

U = 10**5
UU = 2*U
N,A,B,C = map(int,input().split())
pow_A = [1] * (U+1)
pow_B = [1] * (U+1)
pow_AB = [1] * (U+1)
for n in range(1,U+1):
  pow_A[n] = (pow_A[n-1]*A)%MOD
  pow_B[n] = (pow_B[n-1]*B)%MOD
  pow_AB[n] = (pow_AB[n-1]*(A+B))%MOD

fact = [1] * (UU+1)
for n in range(1,UU+1):
  fact[n] = (n*fact[n-1])%MOD
fact_inv = [1] * (UU+1)
fact_inv[UU] = inv_mod(fact[UU])
for n in range(UU,0,-1):
  fact_inv[n-1] = (n*fact_inv[n])%MOD

def comb(n,k):
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

num = 0 # 分母を(A+B)^Nと見て分子
for k in range(N):
  # N-1勝k敗になった後1勝
  x = comb(N-1+k,k)
  x *= pow_B[k]
  x %= MOD
  x *= pow_A[N]
  x %= MOD
  x *= pow_AB[N-k]
  x %= MOD
  x *= (N+k)
  x %= MOD
  num += x
  
for k in range(N):
  # N-1勝k敗になった後1勝
  x = comb(N-1+k,k)
  x *= pow_A[k]
  x %= MOD
  x *= pow_B[N]
  x %= MOD
  x *= pow_AB[N-k]
  x %= MOD
  x *= (N+k)
  x %= MOD
  num += x

# 分母は(A+B)^N
den = pow(A+B,N+N,MOD)

answer = num * inv_mod(den)
answer %= MOD

# 最後に引き分けの補正
answer *= inv_mod(A+B)
answer %= MOD
answer *= 100
answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7
MAX = int(1e5) * 2


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, C = map(int, input().split())
    DIV = div(1, A+B)
    XA = [1] * (N+1)
    XB = [1] * (N+1)
    for i in range(1, N+1):
        XA[i] = XA[i-1] * A * DIV % MOD
        XB[i] = XB[i-1] * B * DIV % MOD
    ans = 0
    for i in range(N, N*2):
        # nCr
        n = i - 1
        r = i - N
        tmpa = i * (XA[N] * XB[i-N]) * FACT[n] * INV[r] * INV[n-r] % MOD
        tmpb = i * (XB[N] * XA[i-N]) * FACT[n] * INV[r] * INV[n-r] % MOD
        ans = (ans + tmpa + tmpb) % MOD
    ans = ans * div(1, 100-C) * 100 % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

m = max(2*N+10,101)
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod
def pow_mod(x,n):
    if n==0: return 1
    if n%2:return x*pow_mod(x,n-1)%mod
    a = pow_mod(x,n//2)
    return a*a%mod

M = A+B
a = A*ninv[M]%mod
b = B*ninv[M]%mod
aN = pow_mod(a,N)
bN = pow_mod(b,N)
ans = 0
for i in range(N):
    ans += (((N+i)*aN%mod)*pow_mod(b,i)%mod)*comb(N-1+i,i)%mod
    ans += (((N+i)*bN%mod)*pow_mod(a,i)%mod)*comb(N-1+i,i)%mod
    ans %= mod
ans = ans*100*ninv[100-C]%mod
print(ans)

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))
        )

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


f = [ModInt(1)]
for i in range(1, 2 * N + 1):
    f.append(f[-1] * i)


def cmb(n, k):
    return f[n] / (f[k] * f[n - k])


c = ModInt(100 - C)
pa = A / c
pb = B / c
ec = 100 / c

ans = sum(
    cmb((N - 1) + i, i) * (N + i) * ec * (pa**N * pb**i + pa**i * pb**N)
    for i in range(N)
)
print(ans)

Submission status: Accepted

Solution code:

# 拡張ユークリッド互除法
# 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

from itertools import accumulate, repeat, chain

MOD = 10**9+7


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

r = 100*modinv(100-C, MOD) % MOD
a = A*modinv(100, MOD)*r % MOD
b = B*modinv(100, MOD)*r % MOD

ap = tuple(chain((1,),accumulate(repeat(a,N),lambda x,y: x*y % MOD)))
bp = tuple(chain((1,),accumulate(repeat(b,N),lambda x,y: x*y % MOD)))

# print(a,b,ap,bp)

def it():
    numer = N
    denom = 1
    for m in range(N):
        yield numer*denom*(ap[N]*bp[m]+ap[m]*bp[N]) % MOD
        numer *= N+m+1
        numer %= MOD
        denom *= modinv(m+1, MOD)
        denom %= MOD


print(sum(it())*r % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,A,B,C = inpl()

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

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

bunbo = pow(A+B,2*N,mod)
bunsi = 0

facAB = [1]*(N+1)
facA  = [1]*(N+1)
facB  = [1]*(N+1)
for i in range(1,N+1):
    facAB[i] = facAB[i-1] * (A+B) %mod
    facA[i] = facA[i-1] * (A) %mod
    facB[i] = facB[i-1] * (B) %mod

# aoki
for i in range(N):
    tmp = (N+i) * facAB[N-i] %mod * Comb(N-1+i,i) %mod
    tmp1 = tmp * facA[N] * facB[i] %mod
    tmp2 = tmp * facB[N] * facA[i] %mod
    bunsi += tmp1 + tmp2
    bunsi %= mod

bunsi *= 100
bunbo *= (A+B)

ans = bunsi * pow(bunbo,mod-2,mod) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

MM = 2 * 10**5
MOD = 10**9 + 7

fact = [1] * MM
for i in range(1, MM): fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MM; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MM-2, -1, -1): invfact[i] = invfact[i+1] * (i+1) % MOD

def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD if 0 <= k <= n else 0

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

N, A, B, C = reads()

invh = inv(100)

pA = A * inv(A + B) % MOD
pB = B * inv(A + B) % MOD

powpA = [1] * (N+1)
for i in range(1, N+1):
  powpA[i] = (powpA[i-1] * pA) % MOD

powpB = [1] * (N+1)
for i in range(1, N+1):
  powpB[i] = (powpB[i-1] * pB) % MOD

expc = 100 * inv(A + B) % MOD

expect = 0
for i in range(N):
  cb = comb(N-1  + i, i)
  expect += (N + i) * expc % MOD * cb % MOD * powpA[N] * powpB[i] % MOD
  expect %= MOD
  expect += (N + i) * expc % MOD * cb % MOD * powpA[i] * powpB[N] % MOD
  expect %= MOD

print(expect)

Submission status: Accepted

Solution code:
mod=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,mod)[0]%mod
N,A,B,C=map(int,input().split())
ONE=(100*inv(100-C))%mod
P=(A*inv(A+B))%mod
Q=(B*inv(A+B))%mod
MAX_N=200000
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1;Finv[0]=1
for i in range(MAX_N):
    Fact[i+1]=((i+1)*Fact[i])%mod
    Finv[i+1]=inv(Fact[i+1])
def Comb(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%mod)%mod
PN=[0 for i in range(N+1)]
QN=[0 for i in range(N+1)]
PN[0]=1
QN[0]=1
for i in range(N):
    PN[i+1]=(P*PN[i])%mod
    QN[i+1]=(Q*QN[i])%mod
ans=0
for M in range(N):
    ans+=((M+N)*(PN[N]*(QN[M]*Comb(M+N-1,M))%mod)%mod)%mod
    ans%=mod
    ans+=((M+N)*(QN[N]*(PN[M]*Comb(M+N-1,M))%mod)%mod)%mod
    ans%=mod
print((ans*ONE)%mod)

Submission status: Runtime Error

Solution code:
    mod = 10**9+7
    fact = [1]*200001
    for i in range(1, 200001):
        fact[i] = fact[i-1]*i % mod

    def inv_n(n, mod=10**9+7): return pow(n, mod-2, mod)
    def nCr(n, r, mod=10**9 +
            7): return inv_n(fact[n-r]*fact[r] % mod, mod)*fact[n] % mod

    n, a, b, c = map(int, input().split())
    ans = 0
    for i in range(n, 2*n):
        j = i*100*inv_n(a+b) % mod
        ans = (ans + j*nCr(i-1, n-1)*(pow(a, n, mod)*pow(b, i-n, mod) +
                                      pow(a, i-n, mod)*pow(b, n, mod))*inv_n(pow(a+b, i, mod))) % mod
    print(ans)


main()

Submission status: Runtime Error

Solution code:
n,a,b,c=map(int,input().split())
M=10**9+7
m=2*n
fact=[1]*(M+1)
ifact=[1]*(M+1)
r=1
for i in range(1,m+1):fact[i]=r=r*i%M
ifact[m]=r=pow(fact[m],M-2,M)
for i in range(m,0,-1):ifact[i-1]=r=r*i%M
r=pow(a+b,M-2,M) 
p=0
d=b*r%M
e=1
for k in range(n):
    v=fact[n+k-1]*ifact[n-1]*ifact[k]%M*e*(n+k)%M
    e=e*d%M
    p+=v
p*=pow(a*r%M,n,M)*100*r%M
q=0
d=a*r%M
e=1
for k in range(n):
    v=fact[n+k-1]*ifact[n-1]*ifact[k]%M*e*(n+k)%M
    e=e*d%M
    q+=v
q*=pow(b*r%M,n,M)*100*r%M
print((p+q)%M)

Submission status: Runtime Error

Solution code:
# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(100)
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(2 * N)
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(100, 2 * N)
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
import sys
input = sys.stdin.readline


def cmb(n, r):
	r = min(n - r, r)
	if r == 0:
		return 1
	numer = reduce(mul, range(n, n - r, -1))
	denom = reduce(mul, range(1, r + 1))
	return numer // denom


N, A, B, C = map(int, input().split())
ans = 0
for k in range(N, 2 * N):
	c = cmb(k - 1, N - 1)
	a = ((A / (A + B)) ** N) * ((B / (A + B)) ** (k - N))
	b = ((A / (A + B))** (k - N)) * ((B / (A + B)) ** N)
	ans += (k * (a + b) * c * 100) / (100 - C)
print(int(ans))