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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a,b,c = list(map(int, input().split()))

M = 10**9+7 # 出力の制限
N = max(200, 2*n+10) # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

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

inv = inverse[100]
ans = 0
a,b = 100*a*inverse[100-c], 100*b*inverse[100-c]
for k in range(n):
    pa = (cmb(n+k-1, k, M) * pow(b, k, M) * pow(a, n, M) * pow(inv, n+k, M)) % M
    pb = (cmb(n+k-1, k, M) * pow(a, k, M) * pow(b, n, M) * pow(inv, n+k, M)) % M
    ans += (n+k) * (pa + pb)
    ans %= M
ans *= 100*inverse[100-c]
ans %= M
print(ans%M)

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ex_game = (pow(100-c,mod-2,mod) * 100)%mod
win_a = (pow((a+b),mod-2,mod) * a)%mod
win_b = (pow((a+b),mod-2,mod) * b)%mod

exp_a = [1] * (n+1)
exp_b = [1] * (n+1)

for i in range(1,n+1):
    exp_a[i] = (exp_a[i-1] * win_a)%mod
    exp_b[i] = (exp_b[i-1] * win_b)%mod

ans = 0
for i in range(n):
    #高橋くんwin E(n,i)
    ans += com(i+n-1,i) * exp_a[n] * exp_b[i] * ex_game*(n+i)
    #青木くんwin E(i,n)
    ans += com(i+n-1,i) * exp_b[n] * exp_a[i] * ex_game*(n+i)
    ans %= mod

print(ans)

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

# if(c==0):
#     ex_a,ex_b = 1,1
# else:
#     ex_a = (pow(c,mod-2,mod) * 100)%mod
#     ex_b = (pow(c,mod-2,mod) * 100)%mod
ex_a = (pow(100-c,mod-2,mod) * 100)%mod
ex_b = (pow(100-c,mod-2,mod) * 100)%mod

win_a = (pow((a+b),mod-2,mod) * a)%mod
win_b = (pow((a+b),mod-2,mod) * b)%mod

inv = [0] * 101
for i in range(101):
    inv[i] = pow(i,mod-2,mod)

exp_a = [1] * (n+1)
exp_b = [1] * (n+1)

for i in range(1,n+1):
    exp_a[i] = (exp_a[i-1] * win_a)%mod
    exp_b[i] = (exp_b[i-1] * win_b)%mod

ans = 0
for i in range(n):
    #高橋くんwin E(n,i)
    tmp = com(i+n-1,i) * exp_a[n] * exp_b[i] * (ex_a*n + ex_b*i)
    ans += tmp

    #青木くんwin E(i,n)
    tmp = com(i+n-1,i) * exp_b[n] * exp_a[i] * (ex_a*i + ex_b*n)
    ans += tmp

    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
N, A, B, C = map(int, input().split())
inv100 = pow(100, mod-2, mod)
A = A * inv100 % mod
B = B * inv100 % mod
C = C * inv100 % mod

fact = [1] * (2*N+1)
fact_inv = [1] * (2*N+1)
for i in range(1, 2*N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(1, 2*N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod


def calc(A, B, C):
    ans = 0
    for j in range(N):
        ans += fact[j+N] * fact_inv[N-1] * fact_inv[j] * pow(B, j, mod) * pow(pow(1 - C, mod-2, mod), j + N + 1, mod)
        ans %= mod
    ans = ans * pow(A, N, mod) % mod
    return ans


ans = (calc(A, B, C) + calc(B, A, C)) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)*pow(ab,N-1-i,pr)%pr*(pow(A,N,pr)*pow(B,i,pr)+pow(B,N,pr)*pow(A,i,pr))%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
ap=pow(A,N,pr)
bp=pow(B,N,pr)
abp=1
bap=1
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)%pr*pow(ab,N-1-i,pr)%pr*(ap*abp+bp*bap)%pr
    abp=abp*B%pr
    bap=bap*A%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = 2*10**5+3
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n,a,b,c=map(int,input().split())
ans=0
for i in range(n):#A,B:n勝,i勝
  ans=(ans+pow(a,n,mod)*pow(b,i,mod)*cmb(n-1+i,i)*(n+i)*pow(pow(a+b,mod-2,mod),n+i,mod))%mod
for i in range(n):
  ans=(ans+pow(b,n,mod)*pow(a,i,mod)*cmb(n-1+i,i)*(n+i)*pow(pow(a+b,mod-2,mod),n+i,mod))%mod
print(ans*100*pow(a+b,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算を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 = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

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

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

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


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

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

ec = 100 * pow(100 - c, MOD - 2, MOD) % MOD

ans1 = 0
tmp = pow(pa, n, MOD)
for i in range(n):
    ans1 += tmp * pow(pb, i, MOD) * comb.combination(n - 1 + i, i) * (n + i) * ec
    ans1 %= MOD

ans2 = 0
tmp = pow(pb, n, MOD)
for i in range(n):
    ans2 += tmp * pow(pa, i, MOD) * comb.combination(n - 1 + i, i) * (n + i) * ec
    ans2 %= MOD

print((ans1 + ans2) % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, A, B, C = map(int, input().split())
mod = 10 ** 9 + 7
t = pow(A + B, mod - 2, mod)

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N * 2, mod)
res = 0
for x in range(N):
  res += (N + x) * f.combi(N + x - 1, x) % mod * pow(A, N, mod) % mod * pow(B, x, mod) % mod * pow(t, N + x, mod) % mod * 100 * t % mod
  res %= mod
  res += (N + x) * f.combi(N + x - 1, x) % mod * pow(A, x, mod) % mod * pow(B, N, mod) % mod * pow(t, N + x, mod) % mod * 100 * t % mod
  res %= mod
print(res)

Submission status: Accepted

Solution code:
n_ = 2*10**5 + 10
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod


def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

n,a,b,c = map(int, input().split())
m100 = modinv(a+b, mod)
a = a * m100 % mod
b = b * m100 % 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
ans = 0
for i in range(n, 2*n):
  ans += i * nCr(i-1, n-1)*((pa[n]*pb[i-n] + pb[n]*pa[i-n]) % mod) % mod

print(ans * 100 * modinv(100-c, mod) % mod)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

def inv(a):
    m=10**9+7
    b=m
    (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 % m


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

    frac=[1]
    for i in range(1,2*n):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(2*n)]
    powa,powb,pow100=[1],[1],[1]

    for i in range(n):
        powa.append(powa[-1]*a%MOD)
        powb.append(powb[-1]*b%MOD)
    for i in range(2*n):
        pow100.append(pow100[-1]*(100-c)%MOD)

    ans=0
    
    for m in range(n,2*n):
        tmpp=frac[m-1]*fracinv[n-1]*fracinv[m-n]%MOD*(powa[n]*powb[m-n]+powa[m-n]*powb[n])*m%MOD
        tmpq=pow100[m+1]
        ans=(ans+tmpp*inv(tmpq))%MOD
        
    print(ans*100%MOD)     

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (3 * 10 ** 6)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD

n, a, b, c = map(int, input().split())
x = a * pow(100 - c, MOD - 2, MOD) % MOD
y = b * pow(100 - c, MOD - 2, MOD) % MOD
z = c * pow(100, MOD - 2, MOD) % MOD
ans = 0
fninv = pow(fac[n - 1], MOD - 2, MOD)
ta = pow(x, n, MOD)
for i in range(n):
    ans += (n + i) * ta * pow(y, i, MOD) % MOD * \
        fac[n - 1 + i] * fninv * pow(fac[i], MOD - 2, MOD) % MOD
    ans %= MOD
tb = pow(y, n, MOD)
for i in range(n):
    ans += (n + i) * tb * pow(x, i, MOD) % MOD * \
        fac[n - 1 + i] * fninv * pow(fac[i], MOD - 2, MOD) % MOD
    ans %= MOD
ans *= z * pow((1 - z) % MOD, MOD - 2, MOD) + 1
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
def getCombKs(n, k, invs, MOD):
    combKs = [0] * (n+1)
    combKs[k] = 1
    for x in range(k+1, n+1):
        combKs[x] = (combKs[x-1] * x * invs[x-k]) % MOD
    return combKs
def getPows(base, n, MOD):
    pows = [1] * (n+1)
    for x in range(1, n+1):
        pows[x] = (pows[x-1] * base) % MOD
    return pows

invs = getInvs(N, MOD)
combKs = getCombKs(2*N-1, N-1, invs, MOD)
powAs = getPows(A, N, MOD)
powBs = getPows(B, N, MOD)
invPowABs = getPows(pow(A+B, MOD-2, MOD), 2*N-1, MOD)

ans = 0
for m in range(N, 2*N):
    v = combKs[m-1] * (powAs[N]*powBs[m-N] + powAs[m-N]*powBs[N]) * m * invPowABs[m] % MOD
    ans = (ans+v) % MOD

ans = ans * 100 * pow(A+B, MOD-2, MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,a,b,c=MI()
    a, b = mint(a), mint(b)
    p=a/(a+b)
    pp=[mint(1)]
    for i in range(200005):pp.append(pp[-1]*p)
    q=b/(a+b)
    qq=[mint(1)]
    for i in range(200005):qq.append(qq[-1]*q)
    ans=0
    for m in range(n,2*n):
        ans+=m*100*(pp[n]*qq[m-n]+qq[n]*pp[m-n])*nCr(m-1,n-1)
    ans/=a+b
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, a, b, c = LI()
fac = [1] * (2 * n + 1)
inv = [1] * (2 * n + 1)
for j in range(1, 2 * n + 1):
    fac[j] = fac[j-1] * j % mod

inv[2 * n] = pow(fac[2 * n], mod-2, mod)
for j in range(2 * n - 1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod

memoA = [1] * (n + 1)
memoB = [1] * (n + 1)
for i in range(1, n + 1):
    memoA[i] = memoA[i - 1] * a % mod
    memoB[i] = memoB[i - 1] * b % mod

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


ret = 0
for i in range(n, 2 * n):
     numerator = comb(i - 1, n - 1) * (memoA[n] * memoB[i - n] + memoA[i - n] * memoB[n]) * i * 100 % mod
     divisor = pow(pow(a + b, i, mod), mod - 2, mod) * pow(100 - c, mod - 2, mod)
     ret = (ret + numerator * divisor) % mod


print(ret)

Submission status: Accepted

Solution code:
n,a,b,c = map(int, input().split( ))
mod = 10**9+7
#n回～2nー1回
a_ab = pow(a+b,mod-2,mod)*a
prob = pow(a_ab,n,mod)

ans = prob*n
b_ab = pow(a+b,mod-2,mod)*b
for i in range(1,n):
    pre = prob
    prob *= (n+i)
    prob *= pow(i,mod-2,mod)
    prob *= b_ab
    prob %= mod
    ans += (prob-pre*b_ab)*(n+i)
    ans %=mod
prob = pow(b_ab,n,mod)
ans2 = prob*n
for i in range(1,n):
    pre = prob
    prob *= (n+i)
    prob *= pow(i,mod-2,mod)
    prob *= a_ab
    prob %= mod
    ans += (prob-pre*a_ab)*(n+i)
    ans %= mod
ans += ans2
ans *= pow(100-c,mod-2,mod)*100
ans%=mod
print(ans)

Submission status: Accepted

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

MAXN = 200005
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % 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

a = A * inv[A+B]
b = B * inv[A+B]
apow = [1]
bpow = [1]
for _ in range(N+1):
    apow.append((apow[-1] * a) % MOD)
    bpow.append((bpow[-1] * b) % MOD)

ans = 0
for m in range(N,2*N):
    pa = apow[N] * bpow[m-N]
    pb = bpow[N] * apow[m-N]
    tmp = m * comb(m-1, N-1) * (pa + pb)
    ans += tmp
    ans %= MOD
ans *= 100 * inv[100-C]
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
N, A, B, C = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N*2) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N*2)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
res = 0
AB_inv = pow(A+B, mod-2, mod)
for m in range(N, N*2):
    res+=comb(m-1, N-1)*pow(A, N, mod)*pow(B, m-N, mod)*pow(AB_inv, m, mod)*m
    res+=comb(m-1, N-1)*pow(B, N, mod)*pow(A, m-N, mod)*pow(AB_inv, m, mod)*m
    res%=mod
res*=100*pow(100-C, mod-2, mod)
res%=mod
print(res)

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
def inv(x):
  return pow(x,mod-2,mod)

n,a,b,c = map(int,input().split())
num = 0
if a == 0 or b == 0:
  print(n*(max(a,b)+c)*inv(100-c)%mod)
  exit()
for i in range(n):
  num = (num+(i+n)*cmb(n-1+i,i)*pow(a+b,n-i,mod)*(inv(pow(a,n-i,mod))+inv(pow(b,n-i,mod))))%mod
ans = num*inv(pow(a+b,2*n,mod))*pow(a,n,mod)*pow(b,n,mod)*100*inv(100-c)%mod
print(ans)

Submission status: Accepted

Solution code:
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
N, A, B, C = map(int, input().split())
lA = [1]*(N+1)
lB = [1]*(N+1)
lAplusB = [1]*(2*N+1)
for i in range(N):
  lA[i+1] = lA[i]*A%MOD
  lB[i+1] = lB[i]*B%MOD
for i in range(2*N):
  lAplusB[i+1] = lAplusB[i]*(A+B)%MOD
ans = 0
for M in range(N, 2*N):
  num = comb(M-1, N-1) * (lA[N]*lB[M-N] + lA[M-N]*lB[N]) * M * 100
  num %= MOD
  den = lAplusB[M+1]
  ans += num*pow(den, MOD-2, MOD)
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
"""
100/C 回1回の施行にかかる

Aが克orBの場合を愚直に計算

N,b 回でaが勝つ確率(b < N)
nCr(N+b-1,b) * (b/100)^b * (a/100)^N

↑これはもう求めちゃっておく
"""

#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


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

inv100 = inverse(100,mod)
invAB = inverse(A+B,mod)

ans = 0
for b in range(N):

    ans += modnCr(N+b-1,b,mod,fac,inv) * pow(B*invAB,b,mod) * pow(A*invAB,N,mod) * (N+b)
    ans %= mod
    #print (ans)

for a in range(N):

    ans += modnCr(N+a-1,a,mod,fac,inv) * pow(A*invAB,a,mod) * pow(B*invAB,N,mod) * (N+a)
    ans %= mod
    #print (ans)
#print (ans)
print (ans * 100 * inverse(100-C,mod) % mod)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
mod = int(1e+9 + 7)
p = mod - 2
ax = []
while p != 0:
  ax = [p%2] + ax[:]
  p //= 2

def prod(l, num):
  n1 = 1
  for i in range(len(l)):
    if l[i] == 1:
      n1 *= num
      n1 %= mod
    if i != len(l)-1:
      n1 *= n1
      n1 %= mod
  return n1
nn = N - 1
bx = []
while nn != 0:
  bx = [nn%2] + bx[:]
  nn //= 2
invC = prod(ax, 100-C)
AN, BN, CN = 1, 1, prod(bx, 100 - C)
s1, s2 = 0, 0
p1 = 1
for i in range(N):
  p1 *= (i+1)
  p1 %= mod
p2 = p1
for i in range(N):
  s1 += p1 * BN * CN
  s1 %= mod
  s2 += p1 * AN * CN
  s2 %= mod
  if i != N - 1:
    p1 *= (N + 1 + i) * prod(ax, i+1)
    p1 %= mod
  CN *= invC
  CN %= mod
  AN *= A
  AN %= mod
  BN *= B
  BN %= mod

s1, s2 = (N * 100 * AN) * s1, (N * 100 * BN) * s2
S = (s1 + s2) % mod
S *= (prod(bx, (invC*invC)%mod) * prod(ax, p2) * (invC * invC)) % mod
print(S%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,a,b,c = LI()
    inv_100 = pow(100,mod-2,mod)
    a = a*inv_100%mod
    b = b*inv_100%mod
    c = (1-c*inv_100)%mod
    c = pow(c,mod-2,mod)
    fact = [1]
    N = 2*n
    for i in range(1,N+1):
        fact.append(fact[-1]*i%mod)
    inv = [None]*(N+1)
    inv[N] = pow(fact[N], mod-2, mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    fa,fb,fc = pow(b,n,mod),pow(a,n,mod),pow(c,n+1,mod)
    for i in range(n):
        ans += inv[i]*fact[n+i]*fc*(fb+fa)%mod
        ans %= mod
        fa *= a
        fb *= b
        fc *= c
        if fa >= mod:
            fa %= mod
        if fb >= mod:
            fb %= mod
        if fc >= mod:
            fc %= mod
    print(ans*inv[n-1]%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return fact[a]*fact[a-b]*inv[b]%mod

    n,a,b,c = LI()
    inv_100 = pow(100,mod-2,mod)
    a = a*inv_100%mod
    b = b*inv_100%mod
    c = (1-c*inv_100)%mod
    c = pow(c,mod-2,mod)
    fact = [1]
    N = 200000
    for i in range(1,N+1):
        fact.append(fact[-1]*i%mod)
    inv = [None]*(N+1)
    inv[N] = pow(fact[N], mod-2, mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    pa = pow(a,n,mod)
    pb = pow(b,n,mod)
    for i in range(n):
        ans += inv[n-1]*inv[i]*fact[n+i]*pow(c,n+i+1,mod)*(pa*pow(b,i,mod)+pb*pow(a,i,mod))%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
mod = 10**9+7

# コンビネーション
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#互いに素な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=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

# modを取りながらべき乗する
def power_func(a,n,mod=mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res


N, A, B, C = map(int, input().split())
p1 = A*mod_inv(A+B)%mod
p2 = B*mod_inv(A+B)%mod

s1 = 0
s2 = 0
a1 = 1
a2 = 1
for k in range(N):
    s1 = (s1 + a1*(N+k)*cmb(N+k-1, k)) % mod
    s2 = (s2 + a2*(N+k)*cmb(N+k-1, k)) % mod   
    a1 = a1*p1%mod
    a2 = a2*p2%mod

p = (power_func(p1, N)*s2 % mod + power_func(p2, N)*s1 % mod) % mod
p = (p * mod_inv(A+B) * 100) % mod
print(p)

Submission status: Accepted

Solution code:
def main():
    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())
    pan = pow(a, n, mod)
    pbn = pow(b, n, mod)
    ivab = 100*inv_n(a+b) % mod
    ans = 0
    for i in range(n, 2*n):
        ans = (ans + i*ivab*nCr(i-1, n-1)*(pan*pow(b, i-n, mod) +
                                           pow(a, i-n, mod)*pbn)*inv_n(pow(a+b, i, mod))) % mod
    print(ans)


main()