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

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

def makefactable(MAX,p):
    fac = [1,1]+[0]*(MAX-2)
    inv = [0,1]+[0]*(MAX-2)
    finv = [1,1]+[0]*(MAX-2)
    for i in range(2,MAX):
        fac[i] = fac[i - 1] * i % p
        inv[i] = p - inv[p%i] * (p // i) % p
        finv[i] = finv[i - 1] * inv[i] % p
    return fac,inv,finv
fac = makefactable(n*2+10,p)[0]
inv = makefactable(n*2+10,p)[1]
finv= makefactable(n*2+10,p)[2]

def makecontable():
    l = [1]*n
    for i in range(n):
        l[i] = (fac[n+i]*finv[i]*finv[n])%p
    return l
combo = makecontable()


def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


cnt = 0
for k in range(n):
    ans = 1
    ans *= combo[k]
    ans *= power_func(a+b,n-k,p)
    ans *= power_func(a*b,k,p)
    ans *= (power_func(a,n-k,p)+power_func(b,n-k,p))%p
    cnt = (cnt + ans) %p
    
P = (100*n*cnt)%p
Q = (100-c)*power_func(a+b,2*n,p)

print(P*(power_func(Q,p-2,p)) % p)

Submission status: Time Limit Exceeded

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

def makefactable(MAX,p):
    fac = [1,1]+[0]*(MAX-2)
    for i in range(2,MAX):
        fac[i] = fac[i - 1] * i % p
    return fac
fac = makefactable(n*2+10,p)




def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fac[n]
  b=fac[k]
  c=fac[n-k]
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

cnt = 0
for k in range(n):
    ans = 1
    ans *= comb(n+k,k,p)
    ans *= power_func(a+b,n-k,p)
    ans *= power_func(a*b,k,p)
    ans *= (power_func(a,n-k,p)+power_func(b,n-k,p))%p
    cnt = (cnt + ans) %p
    
P = (100*n*cnt)%p
Q = (100-c)*power_func(a+b,2*n,p)

print(P*(power_func(Q,p-2,p)) % p)

Submission status: Time Limit Exceeded

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


def makefactable(MAX,p):
    fac = [1,1]+[0]*(MAX-2)
    inv = [0,1]+[0]*(MAX-2)
    finv = [1,1]+[0]*(MAX-2)
    for i in range(2,MAX):
        fac[i] = fac[i - 1] * i % p
        inv[i] = p - inv[p%i] * (p // i) % p
        finv[i] = finv[i - 1] * inv[i] % p
    return fac,inv,finv
fac = makefactable(n*2+10,p)[0]
inv = makefactable(n*2+10,p)[1]
finv= makefactable(n*2+10,p)[2]

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fac[n]
  b=fac[k]
  c=fac[n-k]
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

cnt = 0
for k in range(n):
    ans = 1
    ans *= comb(n+k,k,p)
    ans *= power_func(a+b,n-k,p)
    ans *= power_func(a*b,k,p)
    ans *= (power_func(a,n-k,p)+power_func(b,n-k,p))%p
    cnt = (cnt + ans) %p
    
P = (100*n*cnt)%p
Q = (100-c)*power_func(a+b,2*n,p)

print(P*(power_func(Q,p-2,p)) % p)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np


def main():
	class ModuloAddition (Abelian):
		def __init__(self, mod):
			self.mod = mod
		
		def operate(self, x, y):
			return (x + y) % self.mod
		
		@property
		def identity(self):
			return 0
		
		def invert(self, x):
			return (-x) % self.mod
	
	class ModuloMultiplication (Abelian):
		def __init__(self, mod):
			self.mod = mod
		
		def operate(self, x, y):
			return (x * y) % self.mod
		
		@property
		def identity(self):
			return 1
		
		def invert(self, x):
			x %= self.mod
			return self.accumulate(x, self.mod - 2)
	
	INF = 1000000007
	N, A, B, C = map(int, input().split())
	add = ModuloAddition(INF)
	mul = ModuloMultiplication(INF)
	A = mul.operate(A, mul.invert(100 - C))
	B = mul.operate(B, mul.invert(100 - C))
	C = mul.operate(C, mul.invert(100))
	
	FACT = [1]
	A_ACC = [1]
	B_ACC = [1]
	for i in range(1, 2*N):
		FACT.append(mul.operate(FACT[i-1], i))
		A_ACC.append(mul.operate(A_ACC[i-1], A))
		B_ACC.append(mul.operate(B_ACC[i-1], B))
	
	def NCK(n, k):
		if n < k:
			return 0
		return mul.cancel(FACT[n], mul.operate(FACT[n-k], FACT[k]))
		
	
	k = mul.invert(add.cancel(1, C))
	ans = 0
	for i in range(N):
		ans = add.operate(
			ans,
			mul.operate(
				i + N,
				mul.operate(
					NCK(N+i-1, i),
					add.operate(
						mul.operate(
							A_ACC[N],
							B_ACC[i]),
						mul.operate(
							A_ACC[i],
							B_ACC[N])
					)
			)))
	ans = mul.operate(ans, k)
	print(ans)


class IComparable (object):
	def compare(self, x, y):
		return -1 if x < y else 0 if x == y else 1




class LongestMonotonicSubsequenceLength (object):
	'''最長単調部分列長'''
	def __init__(self):
		# lowest_lasts[n] := n文字の単調部分列の末尾のうち、最も順位の低いもの
		self.lowest_lasts = []
	
	def append(self, item):
		'''入力列の末尾に要素を追加する'''
		update_index = bisect.bisect_right(self.lowest_lasts, item)
		if update_index < len(self.lowest_lasts):
			self.lowest_lasts[update_index] = item
		else:
			self.lowest_lasts.append(item)
	
	def extend(self, iterable):
		'''入力列の末尾に要素列を接続する'''
		for item in iterable:
			self.append(item)
	
	@property
	def length(self):
		return len(self.lowest_lasts)


import abc


class IBinaryOperator (object, metaclass=abc.ABCMeta):
	@abc.abstractclassmethod
	def operate(self, x, y):
		raise NotImplementedError


class IAssociative (IBinaryOperator):
	def _right_accumulate(self, base, x, count):
		if count < 0:
			raise ValueError('累積回数に負の値が指定されました。')
		acc = base
		while count:
			if count & 1:
				acc = self.operate(acc, x)
			count >>= 1
			x = self.operate(x, x)
		return acc
	
	def accumulate(self, x, count):
		if count < 1:
			raise ValueError('累積回数に負の値またはゼロが指定されました。')
		return self._right_accumulate(x, x, count - 1)


class ICommutative (IBinaryOperator):
	pass


class IIdentitive (IBinaryOperator):
	@abc.abstractproperty
	def identity(self):
		raise NotImplementedError


class IInvertible (IBinaryOperator):
	@abc.abstractmethod
	def invert(self, x):
		raise NotImplementedError


class ILeftCancellative (IBinaryOperator):
	@abc.abstractmethod
	def left_cancel(self, x, y):
		raise NotImplementedError


class IRightCancellative (IBinaryOperator):
	@abc.abstractmethod
	def right_cancel(self, x, y):
		raise NotImplementedError


class ICancellative (ILeftCancellative, IRightCancellative):
	@abc.abstractmethod
	def cancel(self, x, y):
		raise NotImplementedError
	
	def left_cancel(self, x, y):
		return self.cancel(y, x)
	
	def right_cancel(self, x, y):
		return self.cancel(x, y)


class Magma (IBinaryOperator):
	pass


class SemiGroup (Magma, IAssociative):
	pass


class Monoid (SemiGroup, IIdentitive):
	pass


class QuasiGroup (Magma, ICancellative):
	pass


class Loop (QuasiGroup, IIdentitive, IInvertible):
	def invert(self, x):
		return self.cancel(self.identity, x)


class Group (Monoid, Loop, IInvertible):
	def cancel(self, x, y):
		return self.operate(x, self.invert(y))
	
	def accumulate(self, x, count):
		if count < 0:
			x = self.invert(x)
			count = -count
		return self._right_accumulate(self.identity, x, count)


class Abelian (Group, ICommutative):
	pass


class Addition (Abelian):
	'''加算'''
	def operate(self, x, y):
		return x + y
	
	@property
	def identity(self):
		return 0
	
	def invert(self, x):
		return -x
	
	def cancel(self, x, y):
		return x - y
	
	def accumulate(self, x, count):
		return x * count


class Multiplication (Abelian):
	'''非ゼロに対する乗算'''
	def operate(self, x, y):
		return x * y
	
	@property
	def identity(self):
		return 1.0
	
	def invert(self, x):
		return 1.0 / x
	
	def cancel(self, x, y):
		return x / y
	
	def accumulate(self, x, count):
		return x ** count


from itertools import repeat


class UnionFind (object):
	'''Union-Find 木'''
	def __init__(
			self, op=Addition()):
		if not isinstance(op, Abelian):
			raise RuntimeError('op はアーベル群ではありません。')
		
		self.parent = []
		self.potential = []
		self.op = op
	
	def append(self):
		self.parent.append(-1)
		self.potential.append(self.op.identity)
	
	def extend(self, num_nodes):
		self.parent.extend(repeat(-1, num_nodes))
		self.potential.extend(repeat(self.op.identity, num_nodes))
	
	def root_potential(self, x):
		parent = self.parent[x]
		if 0 <= parent:
			self.parent[x], potential = self.root_potential(parent)
			self.potential[x] = self.op.operate(self.potential[x], potential)
			x = self.parent[x]
		return x, self.potential[x]
	
	def root(self, x):
		return self.root_potential(x)[0]
		
	def size(self, x):
		return -self.parent[self.root(x)]
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(self.potential[y], self.potential[x])
	
	def unite(self, x, y, difference=None):
		if difference is None:
			difference = self.op.identity
		x, px = self.root_potential(x)
		y, py = self.root_potential(y)
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.potential[y] = difference		
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)
		



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction

PRIME = 10 ** 9 + 7

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % PRIME
    elif y % 2 == 0:
        return power(x, y//2)**2 % PRIME
    else:
        return power(x, y//2)**2 * x % PRIME

def inv(a):
    return power(a, PRIME-2)

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

a = Fraction(A, d)
b = Fraction(B, d)
k = Fraction(100, d)

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for n in range(2*N, -1, -1):
    for x in range(0, n+1):
        y = n-x
        if x >= N or y >= N:
            continue
        dp[x][y] = a*dp[x+1][y] + b*dp[x][y+1] + k

P, Q = dp[0][0].numerator, dp[0][0].denominator
print((P * inv(Q)) % PRIME)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce

import numpy as np
MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return (a*b)%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
    return w[0], w[1]

def mod_inv(a):
    x, _  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a * MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200010

fac  = np.zeros(MAX, dtype=int)
finv = np.zeros(MAX, dtype=int)
inv  = np.zeros(MAX, dtype=int)

def COMinit():
    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;

def mod_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;


# s = input()
# n = int(input())
COMinit()
N, A, B, C = list(map(int, input().split()))

a = mod_div(A, 100)
b = mod_div(B, 100)
c = mod_div(C, 100)

k_factor_memo = {}
def k_factor(M):
    if M in k_factor_memo:
        return k_factor_memo[M]
    if C == 100-C:
        res = fac[M+1]

        res = mod_div(res, mod_sub(1,c))
        k_factor_memo[M] = res
        return res
    res = mod_mul(fac[M], mod_div(c, mod_sub(1, mod_mul(2,c))))
    c2 = mod_div(c, mod_sub(1, c))
    c2 = pow(c2, M, MOD)
    c2 = mod_sub(c2, 1)
    res = mod_mul(res, c2)
    res = mod_div(res, mod_sub(1,c))
    k_factor_memo[M] = res
    return res

res = 0
an = pow(a, N, MOD)

for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    # print(tmp)
    tmp = mod_mul(tmp, an)
    # print(tmp)
    tmp = mod_mul(tmp, pow(b, j, MOD))
    # print(tmp)
    tmp = mod_mul(tmp, k_factor(N+j))
    # print(tmp)
    res = mod_add(res, tmp)
# print(res)

bn = pow(b, N, MOD)
for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    tmp = mod_mul(tmp, bn)
    tmp = mod_mul(tmp, pow(a, j, MOD))
    tmp = mod_mul(tmp, k_factor(N+j))
    res = mod_add(res, tmp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce

import numpy as np
MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return (a*b)%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
    return w[0], w[1]

def mod_inv(a):
    x, _  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a * MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200010

fac  = np.zeros(MAX, dtype=int)
finv = np.zeros(MAX, dtype=int)
inv  = np.zeros(MAX, dtype=int)

def COMinit():
    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;

def mod_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;


# s = input()
# n = int(input())
COMinit()
N, A, B, C = list(map(int, input().split()))

a = mod_div(A, 100)
b = mod_div(B, 100)
c = mod_div(C, 100)

k_factor_memo = {}
def k_factor(M):
    if M in k_factor_memo:
        return k_factor_memo[M]
    if C == 100-C:
        res = fac[M+1]

        res = mod_div(res, mod_sub(1,c))
        k_factor_memo[M] = res
        return res
    res = mod_mul(fac[M], mod_div(c, mod_sub(1, mod_mul(2,c))))
    c2 = mod_div(c, mod_sub(1, c))
    c2 = pow(c2, M, MOD)
    c2 = mod_sub(c2, 1)
    res = mod_mul(res, c2)
    res = mod_div(res, mod_sub(1,c))
    k_factor_memo[M] = res
    return res

res = 0
an = pow(a, N, MOD)

for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    # print(tmp)
    tmp = mod_mul(tmp, an)
    # print(tmp)
    tmp = mod_mul(tmp, pow(b, j, MOD))
    # print(tmp)
    tmp = mod_mul(tmp, k_factor(N+j))
    # print(tmp)
    res = mod_add(res, tmp)
print(res)

bn = pow(b, N, MOD)
for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    tmp = mod_mul(tmp, bn)
    tmp = mod_mul(tmp, pow(a, j, MOD))
    tmp = mod_mul(tmp, k_factor(N+j))
    res = mod_add(res, tmp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import Fraction
from copy import copy

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

sub = np.zeros(N + 1)
dp = np.zeros(N + 1)

winA = A / (A + B)
winB = B / (A + B)

for _ in range(1, N + 1):
    for i in range(1, N + 1):
        dp[i] = (dp[i - 1] + 1) * winA + (sub[i] + 1) * winB
    sub = copy(dp)

ans = dp[N]
if C:
    ans *= (100 / C)

ans = Fraction(ans)
num = ans.numerator
den = ans.denominator
inv = pow(den, MOD - 2, MOD)

print((num * inv) % 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
def f(x):
  nn = x
  y = 1
  while True:
    if nn == 1:
      break
    y *= nn
    nn -= 1
  return y
def cc(x,y):
  return f(x) // f(y) // f(x-y)
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) * awin**(n-1) * bwin**i
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1,i) * awin**i * bwin**(n-1)
  bsc += p
  bsc %= m
sc0 = asc * awin + bsc * bwin
sc0 %= m
sc1 = sc0 * 100 * inv(d)
sc1 %= m
print(sc1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction


def main():
    n, a, b, c = map(int, input().split())
    table = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    A = Fraction(a, 100)
    B = Fraction(b, 100)
    K = Fraction(100, 100 - c)

    def exp(i, j):
        if i == n or j == n:
            table[i][j] = Fraction(0)
        else:
            table[i][j] = K * (A * exp(i + 1, j) + B * exp(i, j + 1) + 1)
        return table[i][j]
    r = exp(0, 0)
    k = 1
    P = r.numerator
    Q = r.denominator
    M = 1000000007
    while (P + M * k) % Q != 0:
        k += 1
    print(int((P + M * k) / Q % M))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions


def comb(n,r):
    if n >= r:
        numer = math.factorial(n) % mod
        denom_inv = pow(((math.factorial(r) % mod) * (math.factorial(n-r) % mod)) % mod, mod-2, mod)
        return (numer * denom_inv) % mod
    else:
        return 0


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

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

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

Submission status: Time Limit Exceeded

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

import sys

class bigint:
    primeset = set()
    def __init__(self,n,mod):
        if not mod in bigint.primeset:
            assert mod**2 < sys.maxsize, "modulo is too large"
            bigint.primeset.add(mod)
        #
        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 __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    #
    def __mul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n*other.n,self.mod)
    #
    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) )
#
#::::::::::::::::::::::::::::::::::::::::::::::::::
mod= 10**9 + 7
#
n,a,b,c = [ int(x) for x in sys.stdin.readline().split() ]
h= bigint(100,mod)
pa= bigint(a,mod) / h
pb= bigint(b,mod) / h
pcinv= ( bigint(100-c,mod) / h ) ** (-1)
#
an= pa**n
bn= pb**n
#
ret= bigint(0,mod)
pam= bigint(1,mod)
pbm= bigint(1,mod)
pcm= pcinv**(n+1)
ncm= bigint(1,mod)
#
for m in range(n):
    if m>0:
        ncm= ncm * bigint(n+m,mod) / bigint(m,mod)
        pam= pam * pa
        pbm= pbm * pb
        pcm= pcm * pcinv
    #
    t= an * pbm + bn * pam
    if c!=0: t= t * pcm
    ret= ret + ncm * t
#
print( bigint(n,mod)*ret )

Submission status: Time Limit Exceeded

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 = 10 ** 9 + 7
for num in range(mod):
    if num * q == p:
        print(num)

Submission status: Time Limit Exceeded

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
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= mod_inv(a + b, mod)
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a * mod_inv(a + b, mod)
    bn %= mod
    sum_a += an
    sum_a %= mod
    sum_b += bn
    sum_b %= mod
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: Time Limit Exceeded

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
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= mod_inv(a + b, mod)
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a * mod_inv(a + b, mod)
    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: Time Limit Exceeded

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 = an * a % mod
    an = an * (a + b) % mod
    bn = bn * b % mod
    bn = bn * (a + b) % mod
sum_a = an
sum_b = bn
for i in range(1, n):
    an = an * (n + i) % mod
    an = an * mod_inv(i, mod) % mod
    an = an * b % mod
    an = an * mod_inv(a + b, mod) % mod
    bn = bn * (n + i) % mod
    bn = bn * mod_inv(i, mod) % mod
    bn = bn * a % mod
    bn = bn * mod_inv(a + b, mod) % mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q = q * (a + b) % mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

Submission status: Time Limit Exceeded

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 = an * a * (a + b) % mod
    bn = bn * b * (a + b) % mod
sum_a = an
sum_b = bn
for i in range(1, n):
    an = an * (n + i) * mod_inv(i, mod) * b * mod_inv(a + b, mod) % mod
    bn = bn * (n + i) * mod_inv(i, mod) * a * mod_inv(a + b, mod) % mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q = q * (a + b) % mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

Submission status: Accepted

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

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

A,B=100*A*invmod(A+B),100*B*invmod(A+B)

Apow_list=[]
Bpow_list=[]
Apow=Bpow=1
for _ in range(N+1):
  Apow_list.append(Apow)
  Bpow_list.append(Bpow)
  Apow=(Apow*A)%MOD
  Bpow=(Bpow*B)%MOD

# nCr=n!/r!(n-r)!で計算する関数（計算量n*logMOD）…n,rを変えつつ何度も実行する場合
# 各x!および逆元はテーブルで持っておく
fact_list=[1]
fact_inv_list=[1]
for i in range(1,2*N+1):
  fact_mod=(fact_list[-1]*i)%MOD
  fact_list.append(fact_mod)
  fact_inv_list.append(invmod(fact_mod))
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  else:
    return 0
  
answer=0
for M in range(N,2*N):
  bunshi=comb_mod_table(M-1,N-1)
  bunshi*=(Apow_list[N]*Bpow_list[M-N]+Apow_list[M-N]*Bpow_list[N])*M
  bunshi%=MOD  
  bumbo=pow(100,M-1,MOD)*(100-C)%MOD
  term=(bunshi*invmod(bumbo))%MOD
  
  #print(M,term,bunshi,bumbo)
  answer=(answer+term)%MOD
  
print(answer)

Submission status: Accepted

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

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

a = [None] * (2*N+1)
inva = [None] * (2*N+1)
a[0] = 1

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

inva[2*N] = pow(a[2*N],p-2,p)
for i in range(2*N):
    inva[2*N-i-1] = inva[2*N-i] * (2*N-i) % p

ans = 0
prevN = pow(A,N,p) * pow(pow(B,N,p),p-2,p) % p

for m in range(N,2*N):
    tmp = (a[m-1] * inva[N-1] % p) * inva[m-N] % p
    tmp *= m
    tmp %= p
    tmp *= ((pow(A,m-N,p) * pow(B,N,p) % p) + (pow(B,m-N,p) * pow(A,N,p) % p)) % p
    tmp %= p
    ans += tmp
    ans %= p
print(ans * pow(1-C,p-2,p)%p)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

p = 10**9 + 7

N, A, B, C = map(int, input().split())
inv100 = pow(100,p-2,p)
A = A * pow(100-C,p-2,p) % p
B = B * pow(100-C,p-2,p) % p
C = C * inv100 % p
# print(A,B,(1-C)%p)

a = [None] * (2*N+1)
inva = [None] * (2*N+1)
a[0] = 1

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

inva[2*N] = pow(a[2*N],p-2,p)
for i in range(2*N):
    inva[2*N-i-1] = inva[2*N-i] * (2*N-i) % p

ans = 0
prevN = pow(A,N,p) * pow(pow(B,N,p),p-2,p) % p# (A/B)^N

for m in range(N,2*N):
    tmp = (a[m-1] * inva[N-1] % p) * inva[m-N] % p
    # tmp = tmp * ((pow(B,m,p)*prevN % p + pow(A,m,p)*pow(prevN,p-2,p) % p) % p) % p
    tmp *= m
    tmp %= p
    tmp *= ((pow(A,m-N,p) * pow(B,N,p) % p) + (pow(B,m-N,p) * pow(A,N,p) % p)) % p
    tmp %= p
    ans += tmp
    ans %= p
print(ans * pow(1-C,p-2,p)%p)

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b,c=map(int,input().split())
invc=100*pow(100-c,mod-2,mod)
invc%=mod
a*=invc*pow(100,mod-2,mod)
a%=mod
b*=invc*pow(100,mod-2,mod)
b%=mod
fact=[1]
for i in range(1,2*n):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,2*n):
  revfact.append(pow(fact[i],mod-2,mod))
ans=0
for i in range(n,2*n):
  ways_a=fact[i-1]*revfact[n-1]*revfact[i-n]*pow(a,n,mod)*pow(b,i-n,mod)
  ways_b=fact[i-1]*revfact[n-1]*revfact[i-n]*pow(b,n,mod)*pow(a,i-n,mod)
  ans+=i*(ways_a+ways_b)*invc
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#i don't know anything
N,A,B,C = map(int,input().split())

mod = 10**9 + 7

factrial = [1] * (2*N)
pa = [1] * (2*N)
pb = [1] * (2*N)
pab = [1] * (2*N)
for k in range(1, 2*N):
    factrial[k] = (factrial[k-1] * k) % mod
    pa[k] = (pa[k-1] * A) % mod
    pb[k] = (pb[k-1] * B) % mod
    pab[k] = (pab[k-1] * (A+B)) % mod
    
fact_inv = [1] * (2*N)
fact_inv[2*N-1] = pow(factrial[2*N-1], mod - 2, mod)
pab_inv = [1] * (2*N)
pab_inv[2*N-1] = pow(pab[2*N-1], mod - 2, mod)
for k in range(2*N-2, -1, -1):
    fact_inv[k] = (fact_inv[k+1] * (k+1)) % mod
    pab_inv[k] = (pab_inv[k+1] * (A+B)) % mod
 
def comb_mod(n, r, mod=10**9+7):
    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % mod

ans = 0
for m in range(N, 2*N):
    Em = (comb_mod(m-1, N-1) * (pa[N]*pb[m-N] + pa[m-N]*pb[N]) * pab_inv[m] * m * 100 * pow(100-C, mod-2, mod)) % mod

    ans = (ans + Em) % mod

print(ans)

Submission status: Accepted

Solution code:
# C - Best-of-(2n-1)
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


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

X = 0
Y = (100-C)*pow(A+B, 2*N-1, mod)

for i in range(N, 2*N):
    X += pow(A+B, 2*N-1-i, mod)*i*combi.com(i-1, N-1)*(pow(A, N, mod)
                                                       * pow(B, i-N, mod)+pow(B, N, mod)*pow(A, i-N, mod))
    X %= mod
X *= 100
ans = X*pow(Y, mod-2, mod) % mod
print(ans)