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: Wrong Answer

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):
    # print(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
    # print('miss')
    return res

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

res = (C*modinv(100-C)%div)
inv100 = modinv(100-C)
# print("hikiwake: {}".format(res))
memo1 = [1]*(N+1)
memo2 = [1]*(N+1)

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

for i in range(N, 2*N):
    kitai1 = (i*ncr(i-1, N-1)) % div
    # print("{}C{}={} a: {}".format(i,N, ncr(i, N),kitai1))
    # for _ in range(N):
    #     kitai1 = (kitai1*A*inv100) % div
    # for _ in range(i-N):
    #     kitai1 = (kitai1*B*inv100) % div
    kitai1 = (memo1[N]*kitai1)%div
    kitai1 = (memo2[i-N]*kitai1)%div

    # print("kitai a: {}".format(kitai1))
    res += kitai1
    res %= div

for i in range(N, 2*N):
    kitai2 = (i*ncr(i-1, N-1)) % div
    # print(kitai2)
    # for _ in range(N):
    #     kitai2 = (kitai2*B*inv100) % div
    # for _ in range(i-N):
    #     kitai2 = (kitai2*A*inv100) % div
    kitai2 = (memo1[i-N]*kitai2)%div
    kitai2 = (memo2[N]*kitai2)%div
    # print(kitai2)
    res += kitai2
    res %= div

print(res % div)

Submission status: Wrong Answer

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

pa =A/100
pb =B/100
pc =C/100

e = (1/(pa+pb))*N


print(int(e))

Submission status: Wrong Answer

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

def opt(a, b):
    c = gcd(a, b)
    return a//c, b//c

def dot(A, B):
    a = A[0] * B[0]
    b = A[1] * B[1]
    return opt(a, b)

def add(A, B):
    return opt(A[0]*B[1] + B[0]*A[1], A[1] * B[1])

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

A = opt(A, 100)
B = opt(B, 100)
C = opt(C, 100)

g = 1000000007

c = [((1, 1), 0, 0, 0)]
ans = (0, 1)
e = (0, 1)
pi = 0
while pi < len(c):

    PQ, cnt, acnt, bcnt = c[pi]
    pi += 1

    if e[1] > (e[1] - e[0]) * g * 10:
        continue
    if acnt >= N or bcnt >= N:
        e = add(e, PQ)
        ans = add(ans, opt(cnt * PQ[0], PQ[1]))
        continue

    cnt += 1
    c.append((dot(PQ, A), cnt, acnt+1, bcnt))
    c.append((dot(PQ, B), cnt, acnt, bcnt+1))
    c.append((dot(PQ, C), cnt, acnt, bcnt))


print(ans[0]/ans[1])

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
n, a, b, c = list(map(int, input().split()))

a = a * 0.01
b = b * 0.01
c = c * 0.01

e = 0
for k in range(1, 2*n + 1):
    for i in range(k - n):
        e += (a * (n-1) + b * i + c *(k-n-i)) * k * 2
        
print(e)
frac = Fraction(e).limit_denominator(1000)
p = frac.numerator
q = frac.denominator
mod = 2 * n
for num in range(mod):
    if num * q % mod:
        print(num)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction


n, a, b, c = list(map(int, input().split()))
x = 10**9 + 7
a = a/100
b = b/100
c = c/100
kitaiti = 0
for i in range(100000):
    kitaiti += (i+n)*((c**i)*(a**n) + (c**i)*(b**n))
print(round(kitaiti, 10).as_integer_ratio())
p, q = round(kitaiti, 10).as_integer_ratio()[0], round(kitaiti, 3).as_integer_ratio()[1]

for i in range(x-1):
    print(i * q % x == p)
    if  i * q % x == p:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
from fractions import Fraction

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

def nPowSum(m,x,y):
    sum = Fraction(0,1)
    for i in range(m + 1):
        sum = sum + ((x ** i) * (y ** (m - i)))
    return sum


a_p = Fraction(a,100)
b_p = Fraction(b,100)
c_p = Fraction(c,100)
s = Fraction(0,1)
M = ((a_p ** n) * nPowSum(n - 1,b_p,c_p)) + ((b_p ** n) * nPowSum(n - 1,a_p,c_p))
#print(M)
if n >= 2:
    for i in range(n - 2):
        s = s + ((a_p ** n) * nPowSum(i,b_p,c_p))
        s = s + ((b_p ** n) * nPowSum(i,a_p,c_p))
        s = s * (n + i)

#print(s)

s = s + M * Fraction(2 * n - 1,1) / (1 - c_p)
s = s + M * c_p / ((1 - c_p) ** 2)

#print(s)

p = s.numerator
q = s.denominator
k = 0

while True:
    if p % q == 0:
        print(int(p / q))
        break
    else:
        k = k + 1
        p = p + 1000000007

Submission status: Wrong Answer

Solution code:

N,A,B,C = map(int, input().split())
A=A/100
B=B/100
N=N+1
arya = [[0]*N]*N


for i in range(N):
    for j in range(N):
        if i==0 and j==0:
            arya[i][j]=1
        elif i==0 and j!=0:
            arya[i][j] = arya[i][j-1]*A
        elif i!=0 and j ==0:
            arya[i][j] = arya[i-1][j]*B
        elif i==N-1 and j==N-1: arya[i][j]=arya[i-1][j]+arya[i][j-1]
        elif i==N-1 : arya[i][j]=arya[i-1][j]+arya[i][j-1]*A
        elif j==N-1 : arya[i][j]=arya[i-1][j]*B+arya[i][j-1]
        elif 1<=i and 1<=j: arya[i][j]=arya[i-1][j]*B + arya[i][j-1]*A

print(1/arya[N-1][N-1])

Submission status: Wrong Answer

Solution code:
n, a, b, c = map(int, input().split())
e = ((a/100)**n + (b/100)**n) * (n + (c/100)**n / (1 - c/100)**2)
ans = 1
while e*ans - int(e*ans) != 0.0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,a,b,c=(int(i)for i in input().split())
if a>b:
  d=a
else:
  d=b
e=n/(d/100)
for i in range(10**9):
  if ((i+1)*d)%(10**9+7)==(100*n)%(10**9+7):
    print(i+1)
    break

Submission status: Wrong Answer

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

if A == 100 or B == 100:
  print(N)
else:
  A_1 = N * (A / 100) ** N / (1 - B / 100) + (A / 100) ** N * (C / 100) * (1 - (C / 100) ** (N - 1)) / (1 - B / 100) / (1 - C / 100)
  B_1 = N * (B / 100) ** N / (1 - A / 100) + (B / 100) ** N * (C / 100) * (1 - (C / 100) ** (N - 1))/ (1 - A / 100) / (1 - C / 100)
  A_2 = 2 * N * (A / 100) ** N * (C / 100) ** N / (1 - C / 100) + (A / 100) ** N * (C / 100) ** (N + 1) / (1 - C) ** 2
  B_2 = 2 * N * (B / 100) ** N * (C / 100) ** N / (1 - C / 100) + (B / 100) ** N * (C / 100) ** (N + 1) / (1 - C) ** 2
  
  ans = A_1 + B_1 + A_2 + B_2
  print(ans)

Submission status: Wrong Answer

Solution code:
string = input()
sum_of_o = 0
for i in string:
    if i == 'o':
        sum_of_o += 1

if 15-len(string) > 8 - sum_of_o:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
S = input().split(' ')
n = int(S[0])
a = int(S[1])
b = int(S[2])
c = int(S[3])
win = a if a>=b else b

print(int(n*100/win))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, A, B, C = map(int, input().split(" "))
	#N = int(input())
	#S = input()
	#S = input()
	#S = list(S)
	#S = S[:-1]

	AB = (A/100)+(B/100)

	tmp = 0
	if N == 1:
		tmp = (1/AB) * N
	else:
		tmp = (1/AB) * N * 2
		
	print(int(tmp))



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
S = input().split(' ')
n = int(S[0])
a = int(S[1])
b = int(S[2])
c = int(S[3])
win = a if a>=b else b

print(int(n*100/win * (100-c) / 100))

Submission status: Wrong Answer

Solution code:
N, A, B, C = [int(i) for i in input().split()]
P = 0.01*max(A, B)
X = N*(1-P)/P
print(int((N+X)*(1-0.01*C)))

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (2 * n + 2)
fi = [1] * (2 * n + 2)
for i in range(1, 2 * n + 2):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(n):
    ans += (comb(n + i - 1, i) * (pow(a * pow(a + b, mod - 2, mod), n, mod) * pow(b * pow(a + b, mod - 2, mod), i, mod) + pow(b * pow(a + b, mod - 2, mod), n, mod) * pow(a * pow(a + b, mod - 2, mod), i, mod)) * (n + i)) % mod
    ans %= mod
print(ans * 100 * pow(100 - c, mod - 2, mod) % mod)

Submission status: Time Limit Exceeded

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*(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: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

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)

Submission status: Time Limit Exceeded

Solution code:
m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
import math
def cc(x,y):
  ans = 1
  for i in range(y):
    ans *= (x-i) * inv(y-i)
    ans %= m
  return ans
n,a,b,c = map(int,input().split())
d = 100 - c
awin = a * inv(d)
bwin = b * inv(d)
asc = 0
bsc = 0
for i in range(n):
  p = cc(n-1+i,i) * awin**(n-1) * bwin**i * (n+i)
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1+i,i) * awin**i * bwin**(n-1) * (n+i)
  bsc += p
  bsc %= m
sc = asc * awin + bsc * bwin
sc %= m
scn = sc * 100 * inv(d)
scn %= m
print(scn)

Submission status: Time Limit Exceeded

Solution code:
m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
import math
def factorial(t):
  ans = 1
  for i in range(1,t+1):
    ans *= i
    ans %= m
  return ans
def cc(x,y):
  xx = factorial(x) % m
  yy = factorial(y) % m
  xy = factorial(x-y) % m
  return xx * inv(yy) * inv(xy) % m
n,a,b,c = map(int,input().split())
d = 100 - c
awin = a * inv(d)
bwin = b * inv(d)
asc = 0
bsc = 0
for i in range(n):
  p = cc(n-1+i,i) * awin**(n-1) * bwin**i * (n+i)
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1+i,i) * awin**i * bwin**(n-1) * (n+i)
  bsc += p
  bsc %= m
sc = asc * awin + bsc * bwin
sc %= m
scn = sc * 100 * inv(d)
scn %= m
print(scn)

Submission status: Time Limit Exceeded

Solution code:
m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
import math
def cc(x,y):
  xx = math.factorial(x) % m
  yy = math.factorial(y) % m
  xy = math.factorial(x-y) % m
  return xx * inv(yy) * inv(xy) % m
n,a,b,c = map(int,input().split())
d = 100 - c
awin = a * inv(d)
bwin = b * inv(d)
asc = 0
bsc = 0
for i in range(n):
  p = cc(n-1+i,i) * awin**(n-1) * bwin**i * (n+i)
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1+i,i) * awin**i * bwin**(n-1) * (n+i)
  bsc += p
  bsc %= m
sc = asc * awin + bsc * bwin
sc %= m
scn = sc * 100 * inv(d)
scn %= m
print(scn)

Submission status: Time Limit Exceeded

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

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

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

N, A, B, C = mi()

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

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


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

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


print(e)

Submission status: Time Limit Exceeded

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

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

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

N, A, B, C = mi()

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

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


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

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


print(e)

Submission status: Time Limit Exceeded

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

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

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

N, A, B, C = mi()

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

# 累乗を返す sは'a'or'b'(文字列)
#[0]行にはaの階乗を、[1]行にはbの階乗を入れる
powlist = [[-1 for _ in range(N+1)] for _ in range(2)]
def calcpow(i, num, r):
  tmp = powlist[i][r]
  if tmp == -1:
    tmp = (num**r)
    powlist[i][r] = tmp
    return tmp
  else:
    return tmp


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

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

print(e)

Submission status: Time Limit Exceeded

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

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

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

N, A, B, C = mi()

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

# 累乗を返す sは'a'or'b'(文字列)
#[0]行にはaの階乗を、[1]行にはbの階乗を入れる
powlist = [[-1 for _ in range(N+1)] for _ in range(2)]
def calcpow(i, num, r):
  tmp = powlist[i][r]
  if tmp == -1:
    tmp = (num**r)
    powlist[i][r] = tmp
    return tmp
  else:
    return tmp


#cmb(m)でmCn-1を計算
import math
Nmin1fct = math.factorial(N-1)
def cmb(k):
  ans = 1
  for i in range(max(1,k-1),k-N,-1):
    ans = (ans * i) % MOD
  ans = round(ans / Nmin1fct)
  return ans
#cmbの計算終わり

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

print(e)

Submission status: Time Limit Exceeded

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

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


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

Q=pow( 100 , 2*N-1 ,mod)

if C>0: P,Q=Q,P
print ( P*pow(Q, mod-2 , mod) ) % mod

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
size = 50
f = []
invf = []
def inv(n):
  global mod,size
  if n == 1:
    return 1
  k = [0 for i in range(size)]
  a,b,u = mod,n,size
  for i in range(size):
    k[i],a,b = a//b,b,a%b
    if b == 0:
      u = i
      break
  y0,y1 = 1,-k[0]
  for i in range(1,u):
    y0,y1 = y1,y0-k[i]*y1
  while y1 < 0:
    y1 += mod
  return y1%mod
def comb(n,k):
  global mod,f,invf
  if k < 0 or k > n:
    return 0
  if n == 0 and k == 0:
    return 1
  if n == 0:
    return 0
  return (f[n]*((invf[k]*invf[n-k])%mod))%mod
def init(n):
  global mod,f,invf
  f = [0 for i in range(n+1)]
  invf = [0 for i in range(n+1)]
  f[0],invf[0] = 1,1
  for i in range(1,n+1):
    f[i] = (f[i-1]*i)%mod
    invf[i] = inv(f[i])
  
n,a,b,c = map(int,input().rstrip().split())
init(2*n)
m = 0
for k in range(n):
  m = (m+comb(n+k,n)*(pow(a,n,mod)*pow(b,k,mod)+pow(a,k,mod)*pow(b,n,mod))*inv(pow(100-c,n+k+1,mod)))%mod
print((m*n*100)%mod)

Submission status: Time Limit Exceeded

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

#cmb(n, r)でnCrを計算
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
#cmbの計算終わり

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


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

N, A, B, C = mi()

MOD = 10**9+7
a = A * modinv(A+B, MOD)
b = B * modinv(A+B, MOD)
gyakugenofAB = 100 * modinv(A+B, MOD)
#期待値（確率×回数）を足し上げていく。
#N回目～2N-1回目についてループを回す
#m-1Cn-1なことに注意
e = 0
for m in range(N, 2*N):
  e += (m * gyakugenofAB * (cmb(m-1, N-1) % MOD) * ((((a ** N) % MOD) * ((b ** (m-N)) % MOD)) + (((a ** (m-N)) % MOD) * ((b ** N) % MOD)))) % MOD
  e %= MOD

print(e)

Submission status: Time Limit Exceeded

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()))
fact=[1]*(2*N+1)
res = 0
invAB = modinv(A+B)
reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

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

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

for i in range(N, 2*N):
    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: Time Limit Exceeded

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
    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) * P * comb * PA
        ans %= MOD
        P *= B
        P *= rev_mod(A + B)
        P %= MOD
        comb *= N + i
        comb *= rev_mod(i + 1)
        comb %= MOD
    A, B = B, A
print ans

Submission status: Time Limit Exceeded

Solution code:
import math

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


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

def dot(A, B):
    return A * B % g

def po(A, B):

    return pow(A, B, g)

def add(A, B):
    return (A + B) % g

def combi(a, b):
    return fr[a] * div(1, fr[b]) * div(1, fr[a-b]) % g

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



AB = A+B
A = div(A, AB)
B = div(B, AB)
C = div(C, 100)


s = 0
for M in range(N, 2 * N):
    w = dot(add(dot(po(A, N), po(B, M - N)), dot(po(A, M-N), po(B, N))), combi(M-1, N-1) * M * div(1, add(1, -C)))
    s = add(s, w)

print(s)

Submission status: Time Limit Exceeded

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() ]
#n,a,b,c = 100000, 31, 41, 28
#
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)
# 
ret= 0
ncm= 1
for m in range(n):
    if m>0:
        ncm= Mul(ncm,n+m)
        if ncm%m==0: ncm//=m
        else: ncm= Div(ncm,m)
        pam= Mul(pam,pac)
        pbm= Mul(pbm,pbc)
    #
    ret= ( ret + Mul(ncm,pbm+pam) ) % MOD
#
print( ret )

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import Fraction
def combinations_count(n, k):
    return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

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

a = A/(A+B)
b = B/(A+B)
c = C/100
a_N = a**N
b_N = b**N
sum_ex = 0

for i in range(N):
    sum_ex += a**i * b_N * combinations_count(N-1+i,i) * (N+i)*(1/(1-c))
for i in range(N):
    sum_ex += a_N * b**i * combinations_count(N-1+i,i) * (N+i)*(1/(1-c))

P = Fraction(sum_ex).limit_denominator(10000).numerator
Q = Fraction(sum_ex).limit_denominator(10000).denominator

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

mod = 10**9+7
a = P
b = Q

# a/b mod modを求める
mi = modinv(b, mod)
print((a%mod) * mi % mod)