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:
# O(N^2) 解法の供養忘れてた

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

from functools import lru_cache
def main():
    N, A, B, C = map(int, input().split())
    mod = 10**9+7
    comb = Combination(201010)
    AA = A * pow(A+B, mod-2, mod) % mod  # A が勝つ確率
    BB = B * pow(A+B, mod-2, mod) % mod  # B が勝つ確率
    CC = C * pow(100-C, mod-2, mod) % mod  # 引き分けの回数の期待値
    ans = 0
    prob = 0
    for i in range(N):
        p = comb(N-1+i, i) * pow(AA, N-1, mod) % mod * pow(BB, i, mod) % mod * AA % mod
        ans += p * (N+i) % mod * (CC+1) % mod
        prob += p
        p = comb(N-1+i, i) * pow(BB, N-1, mod) % mod * pow(AA, i, mod) % mod * BB % mod
        ans += p * (N+i) % mod * (CC+1) % mod
        prob += p
    print(ans * pow(prob, mod-2, mod) % mod)

main()
exit()

@lru_cache(maxsize=None)
def solve(n, m):
    # 高橋くんが n 回、青木くんが m 回勝つまでの期待値と、そうなる確率
    if n==m==0:
        return 0, 1
    res = prob = 0
    if n > 0:
        e, p = solve(n-1, m)
        p *= AA
        res += p * (e + CC + 1) % mod
        prob += p
    if m > 0:
        e, p = solve(n, m-1)
        p *= BB
        res += p * (e + CC + 1) % mod
        prob += p
    res *= pow(prob, mod-2, mod)
    return res % mod, prob % mod

ans = 0
prob = 0
for i in range(N):
    e, p = solve(N-1, i)
    p *= AA
    ans += p * (e + CC + 1)
    prob += p
    e, p = solve(i, N-1)
    p *= BB
    ans += p * (e + CC + 1)
    prob += p
ans *= pow(prob, mod-2, mod)
print(ans % mod)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

from functools import lru_cache
def main():
    N, A, B, C = map(int, input().split())
    mod = 10**9+7
    comb = Combination(201010)
    AA = A * pow(A+B, mod-2, mod) % mod  # A が勝つ確率
    BB = B * pow(A+B, mod-2, mod) % mod  # B が勝つ確率
    CC = C * pow(100-C, mod-2, mod) % mod  # 引き分けの回数の期待値
    ans = 0
    prob = 0
    for i in range(N):
        p = comb(N-1+i, i) * pow(AA, N-1, mod) % mod * pow(BB, i, mod) % mod * AA % mod
        ans += p * (N+i) % mod * (CC+1) % mod
        prob += p
        p = comb(N-1+i, i) * pow(BB, N-1, mod) % mod * pow(AA, i, mod) % mod * BB % mod
        ans += p * (N+i) % mod * (CC+1) % mod
        prob += p
    print(ans * pow(prob, mod-2, mod) % mod)

main()

Submission status: Accepted

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

fact = [1]*(2*n+10)
for i in range(1,2*n+10):
    fact[i] = fact[i-1]*i%mod

def mod_comb_k(n,k,mod):

    return fact[n] * pow(fact[k], mod - 2, mod) % mod * pow(fact[n-k], mod-2 , mod)

def fa(x):
    return pow(a*pow(a+b,mod-2,mod),x,mod)

def fb(x):
    return pow(b*pow(a+b,mod-2,mod),x,mod)



res = 0
for k in range(n):
    res = (res + (mod_comb_k(n+k-1,k,mod) * (fa(n)*fb(k)%mod + fa(k)*fb(n)%mod) %mod *(n+k)*100%mod) *pow(a+b,mod-2,mod) )%mod
print(res)

Submission status: Accepted

Solution code:
class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

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

a,b = a*pow(a+b, mod-2, mod)%mod, b*pow(a+b, mod-2, mod)%mod
pc = 100*pow(100-c, mod-2, mod)%mod

comb_mod = PERM_COMB_MOD()

ans = 0
for k in range(n, 2*n):
    ans += comb_mod.comb(k-1, n-1) * (pow(a,n,mod)*pow(b,k-n,mod) + pow(a,k-n,mod)*pow(b,n,mod)) * k * pc
    ans %= mod
print(ans)

Submission status: Accepted

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: Accepted

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

MOD = 10**9 + 7
M = 2*N

fact = [1]*(M+1)
rfact = [1]*(M+1)
r = 1
for i in range(1, M+1):
  fact[i] = r = r * i % MOD
rfact[M] = r = pow(fact[M], MOD-2, MOD)
for i in range(M, 0, -1):
  rfact[i-1] = r = r * i % MOD

rev = pow(A+B, MOD-2, MOD)

p = 0
b = B * rev % MOD
e = 1
for k in range(N):
    v = fact[N+k-1] * rfact[N-1] * rfact[k] % MOD
    v = v * e * (N + k) % MOD
    e = e * b % MOD
    p += v
p *= pow(A * rev % MOD, N, MOD) * 100 * rev % MOD

q = 0
b = A * rev % MOD
e = 1
for k in range(N):
    v = fact[N+k-1] * rfact[N-1] * rfact[k] % MOD
    v = v * e * (N + k) % MOD
    e = e * b % MOD
    q += v
q *= pow(B * rev % MOD, N, MOD) * 100 * rev % MOD

print((p + q) % MOD)

Submission status: Accepted

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(max(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: Accepted

Solution code:
mod = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
frac, fraci = frac(341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod
def inv(x):
    if x == 0:
        return inv(100)
    return pow(x, mod-2, mod)

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

pa = A*inv(A+B) %mod
pb = B*inv(A+B) %mod

ans = 0
for i in range(N):
    ans += (N+i)*comb(N-1+i, i)*pow(pa, N, mod)*pow(pb, i, mod)
    ans += (N+i)*comb(N-1+i, i)*pow(pb, N, mod)*pow(pa, i, mod)
    ans %= mod
print(ans*100*inv(100-C)%mod)

Submission status: Accepted

Solution code:
#18:04
n,a,b,c = map(int,input().split())
mod = 10 ** 9 + 7
def inv(x):
  ans = 1
  now = x
  while now != 1:
    ans *= mod // now + 1
    ans %= mod
    now = now - mod % now
  return ans
p = (a * inv(a+b)) % mod
q = (b * inv(a+b)) % mod
taka = 0
aoki = 0
tcom = 1
acom = 1
for i in range(n):
  taka += tcom * (n+i)
  tcom *= n+i
  tcom *= inv(i+1)
  tcom *= q
  tcom %= mod
  aoki += acom * (n+i)
  acom *= n+i
  acom *= inv(i+1)
  acom *= p
  acom %= mod
for _ in range(n):
  taka *= p
  taka %= mod
  aoki *= q
  aoki %= mod
ans = taka + aoki
ans *= 100
ans *= inv(a+b)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
M=10**9+7
def inv(x):return pow(x,M-2,M)
a=A*inv(A+B)
b=B*inv(A+B)
z=0
f=[1]
for i in range(1,2*N):
	f+=f[i-1]*i%M,
def com(n,k):
	return f[n]*inv(f[k])*inv(f[n-k])%M
for i in range(N):
	z+=(N+i)*com(N-1+i,i)*(pow(a,N,M)*pow(b,i,M)+pow(b,N,M)*pow(a,i,M))
	z%=M
print(z*100*inv(100-C)%M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod=10**9+7
n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
n,a,b,c=map(int,input().split())
ans=0
aa,bb=a*pow(a+b,mod-2,mod),b*pow(a+b,mod-2,mod)
an,bn=pow(aa,n,mod),pow(bb,n,mod)
for i in range(n):
  ans+=(n+i)*(an*pow(bb,i,mod)+pow(aa,i,mod)*bn)*comb(n+i-1,i)
  ans%=mod
print((ans*100*pow(100-c,mod-2,mod))%mod)

Submission status: Accepted

Solution code:
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod


N, A, B, C = map(int, input().split())
MOD = 10**9 + 7
com = Combinatorics(2*N, MOD)
pa = A * modular_inverse(A+B, MOD); pb = B * modular_inverse(A+B, MOD);
n_first_AB = (100 * modular_inverse(100 - C, MOD)) % MOD
ans = 0
for m in range(N, 2*N): # E[X] = E_M[ E[X | M] ]
    Exp_X_given_M = (m * n_first_AB) % MOD
    prob_m = com.binom(m-1, N-1) * ((pow(pa, N, MOD) * pow(pb, m-N, MOD)) % MOD + (pow(pa, m-N, MOD) * pow(pb, N, MOD)) % MOD) % MOD
    ans = (ans + Exp_X_given_M * prob_m) % MOD
print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
MOD = 10**9+7
fact_list = [1]
for i in range(1, 2*N):
    fact_list.append(fact_list[-1]*i % MOD)
def div_mod(x, MOD=MOD):
    return pow(x, MOD-2, MOD)
def comb(n, r, MOD=MOD):
    ret = fact_list[n]*div_mod(fact_list[n-r])*div_mod(fact_list[r])
    return ret % MOD
ans = 0
for M in range(N, 2*N):
    temp = (((pow(A, N, MOD)*pow(B, M-N, MOD))% MOD) 
            + ((pow(A, M-N, MOD)*pow(B, N, MOD)) % MOD)) % MOD
    bunshi = (comb(M-1, N-1)*temp*M*100) % MOD
    ans += (bunshi*div_mod(pow(100-C, M+1, MOD))) % MOD
    ans = ans %MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def init_fact_inv(MAX: int, MOD: int) -> list:
    """
    階乗たくさん使う時用のテーブル準備
    MAX：階乗に使う数値の最大以上まで作る
    """
    # 階乗テーブル
    factorial = [1] * MAX
    factorial[0] = factorial[1] = 1
    for i in range(2, MAX):
        factorial[i] = factorial[i-1] * i % MOD
    # 階乗の逆元テーブル
    inverse = [1] * MAX
    # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
    inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
    for i in range(MAX-2, 0, -1):
        # 最後から戻っていくこのループならMAX回powするより処理が速い
        inverse[i] = inverse[i+1] * (i+1) % MOD
    return factorial, inverse

# 組み合わせの数(必要な階乗と逆元のテーブルを事前に作っておく)
def nCr(n, r, factorial, inverse):
    if n < r: return 0
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % MOD
    return numerator * denominator % MOD

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

N,A,B,C=MAP()

fact,inv=init_fact_inv(N*2+1, MOD)

# MODの割り算
AAB=fermat(A, A+B, MOD)
BAB=fermat(B, A+B, MOD)

ans=0
for m in range(N, N*2):
    # (引き分けを考えずに)m回で終わる確率
    x=(pow(AAB, N, MOD) * pow(BAB, m-N, MOD) + pow(BAB, N, MOD) * pow(AAB, m-N, MOD)) * nCr(m-1, N-1, fact, inv)
    # 引き分け以外の試合がm回行われるまでの試合数の期待値
    y=fermat(m*100, A+B, MOD)
    ans=(ans+x*y)%MOD
print(ans)

Submission status: Accepted

Solution code:
M=10**9+7
N,A,B,C=map(int,input().split())
f=[1]
for i in range(1,2*N):
	f.append(f[-1]*i%M)
t=pow(A+B,M-2,M)
A*=t
B*=t
a=pow(A,N,M)
b=pow(B,N,M)
z=0
for i in range(N):
	z+=100*t*f[N+i]*pow(f[N-1]*f[i],M-2,M)*(a+b)
	z%=M
	a=a*B%M
	b=b*A%M
print(z)

Submission status: Accepted

Solution code:
M=10**9+7
N,A,B,C=map(int,input().split())
f=[1]
for i in range(1,2*N):
	f.append(f[-1]*i%M)
t=pow(A+B,M-2,M)
A*=t
B*=t
a=pow(A,N,M)
b=pow(B,N,M)
z=0
for i in range(N):
	z+=(N+i)*100*t*f[N+i-1]*pow(f[N-1]*f[i],M-2,M)*(a+b)
	z%=M
	a=a*B%M
	b=b*A%M
print(z)

Submission status: Accepted

Solution code:
M=10**9+7
N,A,B,C=map(int,input().split())
f=[1]
for i in range(1,2*N):
	f.append(f[-1]*i%M)
t=pow(A+B,M-2,M)
A*=t
B*=t
a=pow(A,N,M)
b=pow(B,N,M)
z=0
for i in range(N):
	z+=(N+i)*100*pow(100-C,M-2,M)*f[N+i-1]*pow(f[N-1]*f[i],M-2,M)*(a+b)
	z%=M
	a=a*B%M
	b=b*A%M
print(z)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
mod=10**9+7
ans=0
rev100=pow(100,mod-2,mod)
revAB=pow(A+B,mod-2,mod)
revA=A*revAB%mod
revB=B*revAB%mod
revC=pow(100-C,mod-2,mod)
revC=100*revC%mod
kaijo=[1]*(2*N)
for i in range(1,2*N):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*(2*N)
gyaku[2*N-1]=pow(kaijo[2*N-1],mod-2,mod)
for i in range(2*N-1,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
AN=pow(revA,N,mod)
BN=pow(revB,N,mod)
for M in range(N,2*N):
    a=AN*pow(revB,M-N,mod)%mod
    b=BN*pow(revA,M-N,mod)%mod
    c=kaijo[M-1]*gyaku[N-1]*gyaku[M-N]%mod
    d=M*revC
    e=c*d*(a+b)%mod
    ans=(ans+e)%mod
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

sys.setrecursionlimit(2147483647)
INF = float('inf')

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt')


def mod_inv(a):
    """
    a の逆元
    :param int a:
    :return:
    """
    return pow(a, MOD - 2, MOD)


# https://atcoder.jp/contests/abc066/submissions/5721975
def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


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

# R * Q % MOD == P ってことは
# P * inv(Q) % MOD == R なのでこれを求めればいい

# --- ふつうに期待値求めてみる ---
# # 引き分けなしの値にする
# A /= 100 - C
# B /= 100 - C
# C /= 100
#
# # 引き分けなしで A が勝つときの回数の期待値
# a = 0
# for i in range(N):
#     a += A ** N * B ** i * math.factorial(N + i - 1) / math.factorial(N - 1) / math.factorial(i) * (N + i)
# # 引き分けなしで B が勝つときの回数の期待値
# b = 0
# for i in range(N):
#     b += B ** N * A ** i * math.factorial(N + i - 1) / math.factorial(N - 1) / math.factorial(i) * (N + i)
#
# # C 以外が起こる期待値なので 1/(1-C) をかける
# ans = (a + b) / (1 - C)
# print(ans)


# --- 愚直解 ---
# ans = 0
# # 引き分けなしで A が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(A * mod_inv(100 - C), N, MOD) \
#            * pow(B * mod_inv(100 - C), i, MOD) \
#            * math.factorial(N + i - 1) \
#            * mod_inv(math.factorial(N - 1) * math.factorial(i)) \
#            * (N + i)
#     ans %= MOD
# # 引き分けなしで B が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(B * mod_inv(100 - C), N, MOD) \
#            * pow(A * mod_inv(100 - C), i, MOD) \
#            * math.factorial(N + i - 1) \
#            * mod_inv(math.factorial(N - 1) * math.factorial(i)) \
#            * (N + i)
#     ans %= MOD
# # 引き分けを考慮
# ans *= 100 * mod_inv(100 - C)
# print(ans % MOD)


# invs = mod_invs(max=max(N, 100), mod=MOD)
# fs = factorials(max=2 * N, mod=MOD)
# ans = 0
# # 引き分けなしで A が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(A * invs[100 - C], N, MOD) \
#            * pow(B * invs[100 - C], i, MOD) \
#            * fs[N + i - 1] \
#            * mod_inv(fs[N - 1] * fs[i]) \
#            * (N + i)
#     ans %= MOD
# # 引き分けなしで B が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(B * invs[100 - C], N, MOD) \
#            * pow(A * invs[100 - C], i, MOD) \
#            * fs[N + i - 1] \
#            * mod_inv(fs[N - 1] * fs[i]) \
#            * (N + i) % MOD
#     ans %= MOD
# # 引き分けを考慮
# ans *= 100 * invs[100 - C]
# print(ans % MOD)


fs = factorials(max=2 * N, mod=MOD)
A = A * mod_inv(100 - C) % MOD
B = B * mod_inv(100 - C) % MOD
A_powers = list(itertools.accumulate([1] * (N + 1), lambda p, _: p * A % MOD))
B_powers = list(itertools.accumulate([1] * (N + 1), lambda p, _: p * B % MOD))
ans = 0
for i in range(N):
    ans += ((A_powers[N] * B_powers[i] + B_powers[N] * A_powers[i])
            * fs[N + i - 1] * mod_inv(fs[N - 1] * fs[i])
            * (N + i))
    ans %= MOD
# 引き分けを考慮
ans *= 100 * mod_inv(100 - C)
print(ans % MOD)

Submission status: Accepted

Solution code:
import os
import sys

sys.setrecursionlimit(2147483647)
INF = float('inf')

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt')


def mod_inv(a):
    """
    a の逆元
    :param int a:
    :return:
    """
    return pow(a, MOD - 2, MOD)


# https://atcoder.jp/contests/abc066/submissions/5721975
def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


MOD = 10 ** 9 + 7
N, A, B, C = list(map(int, sys.stdin.readline().split()))
# R * Q % MOD == P ってことは
# P * inv(Q) % MOD == R なのでこれを求めればいい

# --- ふつうに期待値求めてみる ---
# # 引き分けなしの値にする
# A /= 100 - C
# B /= 100 - C
# C /= 100
#
# # 引き分けなしで A が勝つときの回数の期待値
# a = 0
# for i in range(N):
#     a += A ** N * B ** i * math.factorial(N + i - 1) / math.factorial(N - 1) / math.factorial(i) * (N + i)
# # 引き分けなしで B が勝つときの回数の期待値
# b = 0
# for i in range(N):
#     b += B ** N * A ** i * math.factorial(N + i - 1) / math.factorial(N - 1) / math.factorial(i) * (N + i)
#
# # C 以外が起こる期待値なので 1/(1-C) をかける
# ans = (a + b) / (1 - C)
# print(ans)


# --- 愚直解 ---
# ans = 0
# # 引き分けなしで A が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(A * mod_inv(100 - C), N, MOD) \
#            * pow(B * mod_inv(100 - C), i, MOD) \
#            * math.factorial(N + i - 1) \
#            * mod_inv(math.factorial(N - 1) * math.factorial(i)) \
#            * (N + i)
#     ans %= MOD
# # 引き分けなしで B が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(B * mod_inv(100 - C), N, MOD) \
#            * pow(A * mod_inv(100 - C), i, MOD) \
#            * math.factorial(N + i - 1) \
#            * mod_inv(math.factorial(N - 1) * math.factorial(i)) \
#            * (N + i)
#     ans %= MOD
# # 引き分けを考慮
# ans *= 100 * mod_inv(100 - C)
# print(ans % MOD)


# invs = mod_invs(max=max(N, 100), mod=MOD)
# fs = factorials(max=2 * N, mod=MOD)
# ans = 0
# # 引き分けなしで A が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(A * invs[100 - C], N, MOD) \
#            * pow(B * invs[100 - C], i, MOD) \
#            * fs[N + i - 1] \
#            * mod_inv(fs[N - 1] * fs[i]) \
#            * (N + i)
#     ans %= MOD
# # 引き分けなしで B が勝つときの回数の期待値
# for i in range(N):
#     ans += pow(B * invs[100 - C], N, MOD) \
#            * pow(A * invs[100 - C], i, MOD) \
#            * fs[N + i - 1] \
#            * mod_inv(fs[N - 1] * fs[i]) \
#            * (N + i) % MOD
#     ans %= MOD
# # 引き分けを考慮
# ans *= 100 * invs[100 - C]
# print(ans % MOD)


invs = mod_invs(max=max(N, 100), mod=MOD)
fs = factorials(max=2 * N, mod=MOD)
ans = 0
for i in range(N):
    ans += ((pow(A * invs[100 - C], N, MOD) * pow(B * invs[100 - C], i, MOD)
             + pow(B * invs[100 - C], N, MOD) * pow(A * invs[100 - C], i, MOD))
            * fs[N + i - 1] * mod_inv(fs[N - 1] * fs[i])
            * (N + i))
    ans %= MOD
# 引き分けを考慮
ans *= 100 * invs[100 - C]
print(ans % MOD)

Submission status: Accepted

Solution code:
N,A,B,C=map(int, input().split())
MOD=10**9+7
max_n=(10**5)*2-1
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD

ans=0
a=pow(A,N,MOD)
b=pow(B,N,MOD)
P=pow(A+B,MOD-2,MOD)
d=pow(P,N,MOD)
ans+=(N*(a+b)*d)%MOD
ans%=MOD
for n in range(1,N):
    a=(a*B)%MOD
    b=(b*A)%MOD
    d=(d*P)%MOD
    ans+=((N+n)*comb(N+n-1,N-1)*(a+b)*d)%MOD
    ans%=MOD
print((ans*100*pow(100-C,MOD-2,MOD))%MOD)

Submission status: Accepted

Solution code:
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

class Comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD



N, A, B, C = list(map(int, input().split()))
MOD = 10 ** 9 + 7
com = Comb(2 * N, MOD)
inv = Inv(MOD)
IL = inv.invL(A + B, 2 * N)
IC = inv.invx(100 - C)
PA = [1] * (N + 1)
PB = [1] * (N + 1)
for i in range(1, N + 1):
  PA[i] = PA[i - 1] * A % MOD
  PB[i] = PB[i - 1] * B % MOD

ans = 0
for i in range(N):
  ans = ans + (N + i) * IC * 100 * PA[N] * PB[i] * IL[N + i] * com.com(N + i - 1, i) % MOD
  ans = ans + (N + i) * IC * 100 * PB[N] * PA[i] * IL[N + i] * com.com(N + i - 1, i) % MOD

print(ans % MOD)