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:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  2 15:02:08 2019

@author: Yamazaki Kenichi
"""

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

#p1,p2のべき乗のリスト
P1, P2 = [1], [1]
for i in range(N+1):
    P1.append(P1[-1] * p1 % mod)
    P2.append(P2[-1] * p2 % mod)

ans = 0
for i in range(N):
    ans += (N+i) * cmb(N+i-1, i, mod) * P1[N] * P2[i]
    ans += (N+i) * cmb(N+i-1, i, mod) * P1[i] * P2[N]
    ans %= mod
ans = ans * g(p3) % mod

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  1 20:46:31 2019

@author: Yamazaki Kenichi
"""
import time

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

tnow = time.time()

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,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
def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

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

#p1,p2のべき乗のリスト
P1, P2 = [1], [1]
for i in range(N+1):
    P1.append(P1[-1] * p1 % mod)
    P2.append(P2[-1] * p2 % mod)

ans = 0
for i in range(N):
    ans += (N+i) * cmb(N+i-1, i, mod) * P1[N] * P2[i]
    ans += (N+i) * cmb(N+i-1, i, mod) * P1[i] * P2[N]
    ans %= mod
ans = ans * g(p3) % mod

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

#tnow = time.time()
#pow(p1,100000)

#tnow2 = time.time()
#tnow3 = time.time()
#print(tnow2 - tnow)
#print(tnow3 - tnow2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

def rev_mod(num):
	pow_num = MOD - 2
	ret = 1
	while pow_num > 0:
		if pow_num % 2:
			ret *= num
			ret %= MOD
		num *= num
		num %= MOD
		pow_num /= 2
	return ret

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

ans = 0

for loop in range(2):
    cnt = 0
    P = 1
    comb = 1
    PA = (A * rev_mod(A + B)) % MOD
    PB = (B * rev_mod(A + B)) % MOD
    PCm = 100 * rev_mod(100 - C) % MOD
    for i in range(N - 1):
        P *= PA
        P %= MOD

    for i in range(N):
        ans += PCm * (N + i) % MOD * P % MOD * comb % MOD * PA
        ans %= MOD
        P *= PB
        P %= MOD
        comb *= N + i
        comb %= MOD
        comb *= rev_mod(i + 1)
        comb %= MOD
    A, B = B, A
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

def rev_mod(num):
	pow_num = MOD - 2
	ret = 1
	while pow_num > 0:
		if pow_num % 2 == 1:
			ret *= num
			ret %= MOD
		num *= num
		num %= MOD
		pow_num /= 2
	return ret

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

ans = 0

for loop in range(2):
    cnt = 0
    P = 1
    comb = 1
    PA = (A * rev_mod(A + B)) % MOD
    PB = (B * rev_mod(A + B)) % MOD
    PCm = 100 * rev_mod(100 - C) % MOD
    for i in range(N - 1):
        P *= PA
        P %= MOD

    for i in range(N):
        ans += PCm * (N + i) % MOD * P % MOD * comb % MOD * PA
        ans %= MOD
        P *= PB
        P %= MOD
        comb *= N + i
        comb %= MOD
        comb *= rev_mod(i + 1)
        comb %= MOD
    A, B = B, A
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

def rev_mod(num):
	pow_num = MOD - 2
	ret = 1
	while pow_num > 0:
		if pow_num % 2 == 1:
			ret *= num
			ret %= MOD
		num *= num
		num %= MOD
		pow_num /= 2
	return ret

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

ans = 0

for loop in range(2):
    cnt = 0
    P = 1
    comb = 1
    PA = (A * rev_mod(A + B)) % MOD
    PB = (B * rev_mod(A + B)) % MOD
    PCm = 100 * rev_mod(100 - C) % MOD
    for i in range(N - 1):
        P *= PA
        P %= MOD

    for i in range(N):
        ans += PCm * (N + i) % MOD * P % MOD * comb % MOD * PA
        ans %= MOD
        P *= PB
        P %= MOD
        comb *= N + i
        comb *= rev_mod(i + 1)
        comb %= MOD
    A, B = B, A
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

def rev_mod(num):
	pow_num = MOD - 2
	mod_num = MOD
	pow_cur = num
	ret = 1
	while pow_num > 0:
		if pow_num % 2 == 1:
			ret *= pow_cur
			ret %= mod_num
		pow_cur *= pow_cur
		pow_cur %= mod_num
		pow_num /= 2
	return ret

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

ans = 0

for loop in range(2):
    cnt = 0
    P = 1
    comb = 1
    PA = (A * rev_mod(A + B)) % MOD
    PB = (B * rev_mod(A + B)) % MOD
    PCm = 100 * rev_mod(100 - C) % MOD
    for i in range(N - 1):
        P *= PA
        P %= MOD

    for i in range(N):
        ans += PCm * (N + i) % MOD * P % MOD * comb % MOD * PA
        ans %= MOD
        P *= PB
        P %= MOD
        comb *= N + i
        comb *= rev_mod(i + 1)
        comb %= MOD
    A, B = B, A
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 = [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)

Submission status: Accepted

Solution code:
div=10**9+7
def modinv(a, m=div):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b 
        a = a^b
        b = a^b
        a = a^b
        u -= t*v
        u = u^v
        v = u^v
        u = u^v
    u %= m 
    if u < 0: u += m
    return u

N,A,B,C=list(map(int,input().split()))
ncr_memo = {}

def ncr(n, r):
    if r == 0: return 1
    if n in ncr_memo:
        return ncr_memo[n]
    if n-1 in ncr_memo:
        ncr_memo[n] = (ncr_memo[n-1]*n*modinv(n-(N-1))) % div
        return ncr_memo[n]
    orn = n

    res = 1
    for i in range(1, r+1):
        res = res*n*modinv(i, div) % div
        n = n-1
    res %= div
    ncr_memo[orn] = res
    return res

for i in range(N, 2*N):
    ncr(i-1, N-1)

res = 0
inv100 = modinv(A+B)

reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

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

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

print(res % div)

Submission status: Accepted

Solution code:
div=10**9+7
def modinv(a, m=div):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b 
        a = a^b
        b = a^b
        a = a^b
        u -= t*v
        u = u^v
        v = u^v
        u = u^v
    u %= m 
    if u < 0: u += m
    return u

N,A,B,C=list(map(int,input().split()))
ncr_memo = {}

def ncr(n, r):
    if r == 0: return 1
    if n in ncr_memo:
        return ncr_memo[n]
    if n-1 in ncr_memo:
        ncr_memo[n] = (ncr_memo[n-1]*n*modinv(n-(N-1))) % div
        return ncr_memo[n]
    orn = n

    res = 1
    for i in range(1, r+1):
        res = res*n*modinv(i, div) % div
        n = n-1
    res %= div
    ncr_memo[orn] = res
    return res

for i in range(N, 2*N):
    ncr(i-1, N-1)

res = 0
inv100 = modinv(A+B)

reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

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

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

print(res  % div)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
#from sympy import isprime

class bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return
    #
    def __str__(self):
        return str(self.n)
    #
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n+other.n,self.mod)
    #
    def __iadd__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n + other.n) % self.mod
        return self
    #
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    #
    def __isub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n - other.n) % self.mod
        return self
    #
    def __mul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n*other.n,self.mod)
    #
    def __imul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = ( self.n * other.n ) % self.mod
        return self
    #
    def __pow__(self,other):
        assert type(other)==int, "power should be integer"
        #
        if other<0: return self ** ( other % ( self.mod-1 ) )
        elif other==0: return bigint(1,self.mod)
        elif other==1: return self
        elif other%2==0:
            tmp= self ** (other//2)
            return bigint( ( tmp.n**2 ) % self.mod,self.mod )
        else:
            tmp= self ** (other//2)
            return bigint( ( tmp.n**2 * self.n ) % self.mod,self.mod )
    #
    def __truediv__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return self * ( other ** (other.mod-2) )
    #
    def __itruediv__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self*= ( other ** (other.mod-2) )
        return self
    #
    def copy(self):
        return bigint(self.n,self.mod)
#
#::::::::::::::::::::::::::::::::::::::::::::::::::
n,a,b,c = [ int(x) for x in sys.stdin.readline().split() ]
h= bigint(100) ** (-1)
pa= bigint(a) * h
pb= bigint(b) * h
cc= ( bigint(100-c) * h ) ** (-1)
# power of n
cn= cc**(n+1)
an= pa**n * cn * bigint(n)
bn= pb**n * cn * bigint(n)
# for A
pam= bn
pac= pa * cc
# for B
pbm= an
pbc= pb * cc
# permutation
mbar = n
perm= [ bigint(1) ]
for m in range(1,n):
    mbar-= 1
    perm.append( perm[m-1]*bigint(mbar) )
perm.reverse()
nfact= perm[0]
#
ret= bigint(0)
ncm= bigint(1)
for m in range(n):
    if m>0:
        ncm*= bigint(n+m)
        pam*= pac
        pbm*= pbc
    #
    ret+= ncm*(pbm+pam)*perm[m]
#
print( ret/nfact )

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys

MOD=10**9 + 7

def Add(n,m):
    return (n+m)%MOD

def Sub(n,m):
    return (n-m)%MOD

def Mul(n,m):
    return (n*m)%MOD

def Pow(n,p):
    if p<0: return Pow(n,  ( p % ( MOD-1 ) ) )
    elif p==0: return 1
    elif p==1: return n
    elif p%2==0:
        tmp= Pow( n,(p//2) ) % MOD
        return tmp**2 % MOD
    else:
        tmp= Pow( n,(p//2) ) % MOD
        return ( n * tmp**2 ) % MOD
    #
    raise ValueError

def Div(n,m):
    return ( n * Pow(m,MOD-2) ) % MOD
#
#::::::::::::::::::::::::::::::::::::::::::::::::::
n,a,b,c = [ int(x) for x in sys.stdin.readline().split() ]
#
h= Div(1,100)
pa= Mul(a,h)
pb= Mul(b,h)
cc= Div( 1,Mul(100-c,h) )
# power of n
cn= Pow(cc,n+1)
t = Mul(cn,n)
an= Mul(Pow(pa,n),t)
bn= Mul(Pow(pb,n),t)
# for A
pam= bn
pac= Mul(pa,cc)
# for B
pbm= an
pbc= Mul(pb,cc)
# permutation
mbar = n
perm= [1]*n
for m in range(1,n):
    mbar-=1
    perm[m]= Mul(perm[m-1],mbar)
perm.reverse()
nfact= perm[0]
#
ret= 0
ncm= 1
for m in range(n):
    if m>0:
        ncm= Mul(ncm,n+m)
        pam= Mul(pam,pac)
        pbm= Mul(pbm,pbc)
    #
    ret= ( ret + Mul(Mul(ncm,pbm+pam),perm[m]) ) % MOD
#
print( Div(ret,nfact) )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

# factorials
_nfact = 2 * (10 ** 5) + 10
facts = [0] * _nfact
t = facts[0] = 1
for i in range(1, _nfact):
    t = (t * i) % MOD
    facts[i] = t
ifacts = [0] * _nfact
t = ifacts[-1] = INV(facts[-1])
for i in range(_nfact - 1, 0, -1):
    t = (t * i) % MOD
    ifacts[i - 1] = t

def binomial(m, n):
    return facts[m] * ifacts[n] * ifacts[m - n]

def main():
    N, A, B, C = LI()
    D = DIV(100, 100 - C)
    ans = 0
    ap, bp, abp = [1], [1], [POW(A + B, N)]
    for _ in range(0, N + 1):
        ap.append(ap[-1] * A % MOD)
        bp.append(bp[-1] * B % MOD)
        abp.append(abp[-1] * (A + B) % MOD)
    for m in range(N, 2 * N):
        x = binomial(m - 1, N - 1) * DIV(
            ap[N] * bp[m - N] % MOD + ap[m - N] * bp[N] % MOD,
            abp[m - N]) % MOD
        y = (m * D) % MOD
        ans = (ans + (x * y) % MOD) % MOD
    return ans

print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

# factorials
_nfact = 2 * (10 ** 5) + 10
facts = [0] * _nfact
t = facts[0] = 1
for i in range(1, _nfact):
    t = (t * i) % MOD
    facts[i] = t
ifacts = [0] * _nfact
t = ifacts[-1] = INV(facts[-1])
for i in range(_nfact - 1, 0, -1):
    t = (t * i) % MOD
    ifacts[i - 1] = t

def binomial(m, n):
    return facts[m] * ifacts[n] * ifacts[m - n]

def main():
    N, A, B, C = LI()
    D = DIV(100, 100 - C)
    ans = 0
    ap, bp, abp = [1], [1], [POW(A + B, N)]
    for _ in range(0, N + 1):
        ap.append(ap[-1] * A % MOD)
        bp.append(bp[-1] * B % MOD)
        abp.append(abp[-1] * (A + B) % MOD)
    for m in range(N, 2 * N):
        x = binomial(m - 1, N - 1) * DIV(
            ap[N] * bp[m - N] + ap[m - N] * bp[N],
            abp[m - N]) % MOD
        y = (m * D) % MOD
        ans = (ans + (x * y) % MOD) % MOD
    return ans

print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

# factorials
_nfact = 2 * (10 ** 5) + 10
facts = [0] * _nfact
facts[0] = 1
for i in range(1, _nfact):
    facts[i] = (facts[i - 1] * i) % MOD
ifacts = [0] * _nfact
ifacts[-1] = INV(facts[-1])
for i in range(_nfact - 1, 0, -1):
    ifacts[i - 1] = (ifacts[i] * i) % MOD

def binomial(m, n):
    return facts[m] * ifacts[n] * ifacts[m - n]

def main():
    N, A, B, C = LI()
    D = DIV(100, 100 - C)
    ans = 0
    ap, bp, abp = [1], [1], [POW(A + B, N)]
    for _ in range(0, N + 1):
        ap.append(ap[-1] * A % MOD)
        bp.append(bp[-1] * B % MOD)
        abp.append(abp[-1] * (A + B) % MOD)
    for m in range(N, 2 * N):
        x = binomial(m - 1, N - 1) * DIV(
            ap[N] * bp[m - N] + ap[m - N] * bp[N],
            abp[m - N]) % MOD
        y = (m * D) % MOD
        ans = (ans + (x * y) % MOD) % MOD
    return ans

print(main())

Submission status: Accepted

Solution code:
import sys

def solve():
    file = sys.stdin.readline
    N, A, B, C = map(int, file().split())
    mod = 7 + 10 ** 9
    nfact = [1] * (2 * N)
    nrev = [1] * (2 * N)
    Apow, Bpow, Hpow = [A] * (2 * N), [B] * (2 * N), [A + B] * (2 * N)
    Apow[0] = 1
    Bpow[0] = 1
    Hpow[0] = 1
    Crev = (pow(100 - C, mod - 2, mod) * 100) % mod
    for i in range(2, 2 * N):
        nfact[i] = (nfact[i-1] * i) % mod
        Apow[i] = (Apow[i-1] * A) % mod
        Bpow[i] = (Bpow[i-1] * B) % mod
        Hpow[i] = (Hpow[i-1] * (A + B)) % mod
    nrev[2 * N - 1] = pow(nfact[2 * N - 1], mod - 2, mod)
    Hpow[2 * N - 1] = pow(Hpow[2 * N - 1] , mod - 2, mod)
    for i in reversed(range(1, 2 * N - 1)):
        nrev[i] = (nrev[i + 1] * (i + 1)) % mod
        Hpow[i] = (Hpow[i + 1] * (A + B)) % mod

    ans = 0
    for i in range(N, 2 * N):
        ans += (((nfact[i-1] * nrev[N-1] * nrev[i-N]) % mod) * ((Apow[N]*Bpow[i-N] + Apow[i-N]*Bpow[N]) % mod) * i * Hpow[i] * Crev) % mod
        ans %= mod
    print(ans)

    return

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

# factorials
_nfact = 2 * (10 ** 5) + 10
facts = [0] * _nfact
facts[0] = 1
for i in range(1, _nfact):
    facts[i] = (facts[i - 1] * i) % MOD

def binomial(m, n):
    return DIV(facts[m], facts[n] * facts[m - n])

def main():
    N, A, B, C = LI()
    D = DIV(100, 100 - C)
    ans = 0
    ap, bp, abp = [1], [1], [POW(A + B, N)]
    for _ in range(0, N + 1):
        ap.append(ap[-1] * A % MOD)
        bp.append(bp[-1] * B % MOD)
        abp.append(abp[-1] * (A + B) % MOD)
    for m in range(N, 2 * N):
        x = binomial(m - 1, N - 1) * DIV(
            ap[N] * bp[m - N] + ap[m - N] * bp[N],
            abp[m - N]) % MOD
        y = (m * D) % MOD
        ans = (ans + (x * y) % MOD) % MOD
    return ans

print(main())

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
P = 10**9+7
fa = [1]
al = A * pow(A + B, P-2, P) % P
be = B * pow(A + B, P-2, P) % P
ga = C * pow(100, P-2, P) % P
for i in range(1, N*2+100):
    fa.append(fa[-1]*i%P)
ans = 0
for i in range(N):
    ans = (ans + fa[N+i-1] * pow((fa[N-1]*fa[i]), P-2, P) * (pow(al, N, P) * pow(be, i, P) + pow(al, i, P) * pow(be, N, P)) * (i+N)) % P
print(ans * pow(1-ga, P-2, P) % P)

Submission status: Accepted

Solution code:
from fractions import Fraction


#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0], w[1]]


# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def comb(N, K):
    return comb_array[N] * comb_inv_array[K] * comb_inv_array[N - K] % mod_num


N, A, B, C = map(int, input().split())
mod_num = 10**9 + 7
mod_array_a = [1] * (N + 1)
mod_array_b = [1] * (N + 1)

j = 1
for i in range(N):
    j = (j * A) % mod_num
    mod_array_a[i + 1] = j
j = 1
for i in range(N):
    j = (j * B) % mod_num
    mod_array_b[i + 1] = j
# print(mod_array_a, mod_array_b)
comb_array = [1] * (2 * N - 1)
j = 1
for i in range(2 * N - 1):
    if i == 0:
        continue
    j = (j * i) % mod_num
    comb_array[i] = j
# print(comb_array)
comb_inv_array = [mod_inv(comb_array[i], mod_num) for i in range(N)]

array_ab_inv = [0] * N

init_ab = pow((A + B), N, mod_num) * (100 - C) % mod_num
array_ab_inv[0] = mod_inv(init_ab, mod_num)
for i in range(1, N):
    init_ab = (init_ab * (A + B)) % mod_num
    array_ab_inv[i] = mod_inv(init_ab, mod_num)

ans = 0
for n in range(N, 2 * N):
    combination = comb(n - 1, N - 1)
    # print(combination)
    AB = (mod_array_a[N] * mod_array_b[n - N] +
          mod_array_a[n - N] * mod_array_b[N]) % mod_num
    # print(AB)
    # print(mod_inv(array_ab_inv[0], mod_num))
    ans += (((((combination * AB) % mod_num) * n * 100) % mod_num
             ) * array_ab_inv[n - N]) % mod_num
    # print("ans=", ans)

print(ans % mod_num)

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    facts = [1]
    t = 1
    for i in range(1, n + 1):
        t = t * i % MOD
        facts.append(t)
    invs = [1] * (n + 1)
    t = pow(t, MOD - 2, MOD)
    invs[n] = t
    for i in range(n, 1, -1):
        t = t * i % MOD
        invs[i - 1] = t
    return facts, invs


n, a, b, c = list(map(int, input().split()))
MOD = 10 ** 9 + 7
facts, invs = prepare(2 * n, MOD)

inv_ab = pow(a + b, MOD - 2, MOD)
a_ab = a * inv_ab % MOD
b_ab = b * inv_ab % MOD

win_a = 0
win_b = 0
exp_a = 1
exp_b = 1
for k in range(n):
    coef = facts[n + k] * invs[k] * invs[n - 1] % MOD
    win_a = (win_a + coef * exp_b) % MOD
    win_b = (win_b + coef * exp_a) % MOD
    exp_a = exp_a * a_ab % MOD
    exp_b = exp_b * b_ab % MOD

win_a = win_a * exp_a % MOD
win_b = win_b * exp_b % MOD

print((win_a + win_b) * 100 * inv_ab % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
MOD = 10**9+7
N, A, B, C = map(int, input().split())


def get_inv(N):
    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

mod_inv = get_inv(max(2*N-1, 100))

a = A*mod_inv[A+B]%MOD
b = B*mod_inv[A+B]%MOD
pa = [1]*(N+1)
pb = [1]*(N+1)
for i in range(N):
    pa[i+1] = (pa[i]*a)%MOD
    pb[i+1] = (pb[i]*b)%MOD

c = 1
ans = pa[N]*N + pb[N]*N
ans %= MOD
for m in range(N+1, N*2):
    c *= (m-1) * mod_inv[m-N]
    c %= MOD
    ans += c * ( pa[N]*pb[m-N] + pb[N]*pa[m-N]) % MOD * m % MOD
    ans %= MOD
print(ans*100*mod_inv[100-C]%MOD)

Submission status: Accepted

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

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
inv_ab = mod_inv(a + b, mod)
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= inv_ab
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a
    bn *= inv_ab
    bn %= mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

k,A,B,C = map(int,input().split())
Max = max(2*k+10,101)
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod

M = A+B
a = A*inv[M]%mod
b = B*inv[M]%mod
E = 0
for n in range(k,2*k):
    E += (((n)*pow(a,k,mod)%mod)*pow(b,n-k,mod)%mod)*Comb(n-1,k-1)%mod
    E += (((n)*pow(b,k,mod)%mod)*pow(a,n-k,mod)%mod)*Comb(n-1,k-1)%mod
    E %= mod
E = E*100*inv[100-C]%mod
print(E)

Submission status: Accepted

Solution code:
def getInv(N):#Qはmod
    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
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
t = 100*modinv[100-C]%Q
ans = 0
nowc = 1
ans = Powa[N]*N + Powb[N]*N
ans %= Q
for k in range(N+1, N*2):
    nowc *= (k-1)*modinv[k-N]
    nowc %= Q
    ans += nowc*( Powa[N]*Powb[k-N] + Powb[N]*Powa[k-N])%Q*k%Q
    ans %= Q
print(ans*t%Q)

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

k,A,B,C = map(int,input().split())
Max = max(2*k+10,101)
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%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*inv[M]%mod
b = B*inv[M]%mod
E = 0
for n in range(k,2*k):
    E += (((n)*pow_mod(a,k)%mod)*pow_mod(b,n-k)%mod)*Comb(n-1,k-1)%mod
    E += (((n)*pow_mod(b,k)%mod)*pow_mod(a,n-k)%mod)*Comb(n-1,k-1)%mod
    E %= mod
E = E*100*inv[100-C]%mod
print(E)

Submission status: Accepted

Solution code:
import numpy as np

INF = 1000000007

def add(x, y):
	return (x + y) % INF

def sub(x, y):
	return (x - y) % INF

def mul(x, y):
	return (x * y) % INF

def power(x, y):
	return pow(x, y, INF)

def div(x, y):
	return mul(x, power(y, INF - 2))


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

FACT = [1]
A_ACC = [1]
B_ACC = [1]
for i in range(1, 2*N):
	FACT.append(mul(FACT[i-1], i))
	A_ACC.append(mul(A_ACC[i-1], A))
	B_ACC.append(mul(B_ACC[i-1], B))

def NCK(n, k):
	if n < k:
		return 0
	return div(FACT[n], mul(FACT[n-k], FACT[k]))
	

k = div(1, sub(1, C))

ans = 0
for i in range(N):
	ans = add(
		ans,
		mul(
			i + N,
			mul(
				NCK(N+i-1, i),
				add(
					mul(A_ACC[N], B_ACC[i]),
					mul(A_ACC[i], B_ACC[N])
				)
		)))
ans = mul(ans, k)
print(ans)