Problem:


Score : 700 points

Problem Statement

Today, Snuke will eat B pieces of black chocolate and W pieces of white chocolate for an afternoon snack.

He will repeat the following procedure until there is no piece left:

Choose black or white with equal probability, and eat a piece of that color if it exists.

For each integer i from 1 to B+W (inclusive), find the probability that the color of the i-th piece to be eaten is black.
It can be shown that these probabilities are rational, and we ask you to print them modulo 10^9 + 7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7
(under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

All values in input are integers.

1 \leq B,W \leq 10^{5}

Input

Input is given from Standard Input in the following format:

B W

Output

Print the answers in B+W lines. In the i-th line, print the probability that the color of the i-th piece to be eaten is black, modulo 10^{9}+7.

Sample Input 1

2 1

Sample Output 1

500000004
750000006
750000006

There are three possible orders in which Snuke eats the pieces:

white, black, black

black, white, black

black, black, white

with probabilities \frac{1}{2}, \frac{1}{4}, \frac{1}{4}, respectively. Thus, the probabilities of eating a black piece first, second and third are \frac{1}{2},\frac{3}{4} and \frac{3}{4}, respectively.

Sample Input 2

3 2

Sample Output 2

500000004
500000004
625000005
187500002
187500002

They are \frac{1}{2},\frac{1}{2},\frac{5}{8},\frac{11}{16} and \frac{11}{16}, respectively.

Sample Input 3

6 9

Sample Output 3

500000004
500000004
500000004
500000004
500000004
500000004
929687507
218750002
224609377
303710940
633300786
694091802
172485353
411682132
411682132



Sample input:
2 1


Sample output:
500000004
750000006
750000006

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x): # y / x
    inv_x = pow(x, MOD - 2, MOD)
    return y * inv_x % MOD

def _get_z(y, x): # y / x
    #inv_x = pow(x, MOD - 2, MOD)
    #return y * inv_x % MOD
    while y % x > 0:
        y += MOD
    return y // x

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

def reduce(y, x):
    tmp = gcd(x, y)
    return (y // tmp, x // tmp)

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def make_comb(n, k):
    ret = [0] * n
    ret[k] = 1
    for i in range(k + 1, n):
        ret[i] = (ret[i - 1] * i) // (i - k)
        ret[i] %= MOD
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    b_comb = make_comb(n, b - 1)
    w_comb = make_comb(n, w - 1)
    par = 1
    for i in range(1, n + 1):
        #print(' ======== i: %d ==============' % i)
        other = par - bb - ww
        #x = (par * 2) % MOD
        x = (par * 2)
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        y %= MOD
        y, x = reduce(y, x)
        ret = get_z(y, x)
        print(ret)
        bb = (bb * 2 + w_comb[i - 1]) % MOD
        ww = (ww * 2 + b_comb[i - 1]) % MOD
        #par = (par * 2) % MOD
        par = (par * 2)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i % mod
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i

# print(de_factorial)

def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]


# print(p)
# print(q)
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = 0
    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    

    print(tmp % mod)

Submission status: Time Limit Exceeded

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i

# print(de_factorial)

def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]

for i in range(1, N+1):
    # 確率はこの表現で本当に正しいのか？
    # p[i-1] と comb(i,B)は排他事象 ではない気がする。
    # comb(i,B)でもi-1 でB食べきってしまう p[i-1] の確率が存在するので　
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

# print(p)
# print(q)
for i in range(1, N+1):
    tmp = 0
    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    

    print(tmp % mod)

Submission status: Time Limit Exceeded

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i

# print(de_factorial)

def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

for i in range(1, N+1):
    # 確率はこの表現で本当に正しいのか？
    # p[i-1] と comb(i,B)は排他事象 ではない気がする。
    # comb(i,B)でもi-1 でB食べきってしまう p[i-1] の確率が存在するので　
    p[i] = p[i-1] + comb(i-1 ,B-1) * pow(de_factorial[2], i, mod)
    q[i] = q[i-1] + comb(i-1 ,W-1) * pow(de_factorial[2], i, mod)

# print(p)
# print(q)
for i in range(1, N+1):
    tmp = 0
    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    

    print(tmp % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x):
    while y % x > 0:
        y += MOD
    return y // x

def simplify(y, x):
    ret = 1
    while y % (1 << ret) == 0:
        ret += 1
    return (y >> (ret - 1), x >> (ret - 1))

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def make_comb(n, k):
    ret = [0] * n
    ret[k] = 1
    for i in range(k + 1, n):
        ret[i] = ret[i - 1] * i // (i - k)
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    b_comb = make_comb(n, b - 1)
    w_comb = make_comb(n, w - 1)
    for i in range(1, n + 1):
        par = 1 << (i - 1)
        other = par - bb - ww
        x = par << 1
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        #y, x = simplify(y, x)
        ret = get_z(y, x)
        print(ret)
        bb = bb * 2 + w_comb[i - 1]
        ww = ww * 2 + b_comb[i - 1]
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x):
    while y % x > 0:
        y += MOD
    return y // x

def simplify(y, x):
    ret = 1
    while y % (1 << ret) == 0:
        ret += 1
    return (y >> (ret - 1), x >> (ret - 1))

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    for i in range(1, n + 1):
        par = 1 << (i - 1)
        other = par - bb - ww
        x = par << 1
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        #y, x = simplify(y, x)
        x %= MOD
        y %= MOD
        ret = get_z(y, x)
        print(ret)
        bb = bb * 2 + comb(i - 1, w - 1)
        ww = ww * 2 + comb(i - 1, b - 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x):
    while y % x > 0:
        y += MOD
    return y // x

def simplify(y, x):
    ret = 1
    while y % (1 << ret) == 0:
        ret += 1
    return (y >> (ret - 1), x >> (ret - 1))

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    for i in range(1, n + 1):
        par = 1 << (i - 1)
        other = par - bb - ww
        x = par << 1
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        y, x = simplify(y, x)
        ret = get_z(y, x)
        print(ret)
        bb = bb * 2 + comb(i - 1, w - 1)
        ww = ww * 2 + comb(i - 1, b - 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x):
    while y % x > 0:
        y += MOD
    return y // x

def simplify(y, x):
    ret = 1
    while y % (1 << ret) == 0:
        ret += 1
    return (y >> (ret - 1), x >> (ret - 1))

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    for i in range(1, n + 1):
        par = 1 << (i - 1)
        other = par - bb - ww
        x = par << 1
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        ret = get_z(y, x)
        print(ret)
        bb = bb * 2 + comb(i - 1, w - 1)
        ww = ww * 2 + comb(i - 1, b - 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
B, W = list(map(int, input().split()))

mod = 1000000007

def mul(a, b):
  return ((a % mod) * (b % mod)) % mod
  
memo={0:1,1:2}
def power2(y):
  if y in memo:
    pass
  elif y % 2 == 0 :
    memo[y] = power2(y//2)**2 % mod
  else            : 
    memo[y] = power2(y//2)**2 * 2 % mod
  return memo[y]
  
#B列目
B_0 = [0 for _ in range(B)] + [1 for _ in range(W)]
B_1 = 1
for i in range(B, W+B-1):
  B_1 = (B_1*i//(i-B+1)) %mod
  B_0[i+1]=(B_0[i]*2 + B_1) %mod

#W列目
W_0 = [0 for _ in range(W)] + [1 for _ in range(B)]
W_1 = 1
for i in range(W, W+B-1):
  W_1 = (W_1*i//(i-W+1)) %mod
  W_0[i+1]=(W_0[i]*2 + W_1) %mod
#print(W_0)

#分母 m
#log2m

for i in range(B+W):
  b = B_0[i]
  w = W_0[i]
  log2m = i
  #print(b,w,log2m)
  
  while not b%2 and not w%2 and log2m:
    b=b//2
    w=w//2
    log2m-=1
  
  p = power2((mod-2)*(log2m+1))
  a = (mul(power2(log2m)-b + w,p))%mod
  print(a)

Submission status: Time Limit Exceeded

Solution code:
B, W = map(int, input().split())


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTableMod(N, mod=10 ** 9 + 7):
    fac = [1 for i in range(N)]
    finv = [1 for i in range(N)]
    inv = [1 for i in range(N)]
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def binomialCoefficient(N, r, mod=10 ** 9 + 7):
    if N < r:
        return 0
    else:
        return fac[N] * (finv[r] * finv[N - r] % mod) % mod


fac, finv = makeTableMod(B+W)
mod = 10 ** 9 + 7


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


def plusFraction(frac1, frac2):
    """
    frac: tuple (numerator, denominator)
    """
    b, a = frac1
    d, c = frac2
    g = gcd(a, c)
    nume = b * (c // g) + d * (a // g)
    deno = (a * c) // g
    g = gcd(nume, deno)
    nume //= g
    deno //= g

    return (nume, deno)


P = [(0, 1)]
Q = [(0, 1)]


for i in range(B + W):
    if i == 0:
        print(500000004)
        continue
    p = plusFraction(P[-1], (binomialCoefficient(i-1, B-1, mod), 2**i))
    q = plusFraction(Q[-1], (binomialCoefficient(i-1, W-1, mod), 2**i))
    P.append(p)
    Q.append(q)
    b, a = p[1]-p[0], p[1]
    d, c = q
    g = gcd(a, c)
    nume = b * (c // g) + d * (a // g)
    deno = ((a * c) // g) * 2
    g = gcd(nume, deno)
    nume //= g
    deno //= g
    ans = unknown(deno, nume)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
B, W = map(int, input().split())


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTableMod(N, mod=10 ** 9 + 7):
    fac = [1 for i in range(N)]
    finv = [1 for i in range(N)]
    inv = [1 for i in range(N)]
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def binomialCoefficient(N, r, mod=10 ** 9 + 7):
    if N < r:
        return 0
    else:
        return fac[N] * (finv[r] * finv[N - r] % mod) % mod


fac, finv = makeTableMod(B+W)
mod = 10 ** 9 + 7
P = [Fraction(0, 1)]
Q = [Fraction(0, 1)]


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


for i in range(B + W):
    if i == 0:
        print(500000004)
        continue
    p = Fraction(P[-1]) + Fraction(binomialCoefficient(i - 1, B - 1, mod), 2 ** i)
    q = Fraction(Q[-1]) + Fraction(binomialCoefficient(i - 1, W - 1, mod), 2 ** i)
    P.append(p)
    Q.append(q)
    ans = Fraction((1 - Fraction(P[-1]) + Fraction(Q[-1])), 2)
    bunshi, bunbo = ans.numerator, ans.denominator
    ans = unknown(bunbo, bunshi)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
B, W = map(int, input().split())


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTableMod(N, mod=10**9+7):
    table = [1]
    for i in range(1, N+1):
        table.append((table[-1]*i)%mod)
    return table


def binomialCoefficient(N, r, MOD=1):
    if MOD == 1:
        return int(table[N] / (table[N - r] * table[r]))
    else:
        return int(table[N] / (table[N - r] * table[r])) % MOD


table = makeTableMod(B+W)
mod = 10 ** 9 + 7
P = [Fraction(0, 1)]
Q = [Fraction(0, 1)]


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


for i in range(B + W):
    if i == 0:
        print(500000004)
        continue
    p = Fraction(P[-1]) + Fraction(binomialCoefficient(i - 1, B - 1, mod), 2 ** i)
    q = Fraction(Q[-1]) + Fraction(binomialCoefficient(i - 1, W - 1, mod), 2 ** i)
    P.append(p)
    Q.append(q)
    ans = Fraction((1 - Fraction(P[-1]) + Fraction(Q[-1])), 2)
    bunshi, bunbo = ans.numerator, ans.denominator
    ans = unknown(bunbo, bunshi)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
B, W = map(int, input().split())


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTable(N):
    table = [1]
    for i in range(1, N+1):
        table.append(table[-1]*i)
    return table


def binomialCoefficient(N, r, MOD=1):
    if MOD == 1:
        return int(table[N] / (table[N - r] * table[r]))
    else:
        return int(table[N] / (table[N - r] * table[r])) % MOD


table = makeTable(B+W)
mod = 10 ** 9 + 7
P = [Fraction(0, 1)]
Q = [Fraction(0, 1)]


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


for i in range(B + W):
    if i == 0:
        print(500000004)
        continue
    p = Fraction(P[-1]) + Fraction(binomialCoefficient(i - 1, B - 1, mod), 2 ** i)
    q = Fraction(Q[-1]) + Fraction(binomialCoefficient(i - 1, W - 1, mod), 2 ** i)
    P.append(p)
    Q.append(q)
    ans = Fraction((1 - Fraction(P[-1]) + Fraction(Q[-1])), 2)
    bunshi, bunbo = ans.numerator, ans.denominator
    ans = unknown(bunbo, bunshi)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 30 22:26:37 2019

@author: Owner
"""

MOD = 1000000007

def inv(x):
    return pow(x, MOD - 2, MOD)

B, W = map(int, input().split())
fct = [1] * (B + W + 1)
for i in range(B + W):
    fct[i + 1] = (fct[i] * (i + 1)) % MOD

def c(n, k):
    return (fct[n] * inv(fct[k]) * inv(fct[n - k])) % MOD

#p[i]: 黒B回白i回の確率
#q[i]: 黒i回白W回の確率
p = [0] * W
p[0] = inv(pow(2, B, MOD))
for i in range(W - 1):
    p[i + 1] = (p[i] + c(B + i, i + 1) * inv(pow(2, B + i, MOD)) * inv(2)) % MOD
q = [0] * B
q[0] = inv(pow(2, W, MOD))
for i in range(B - 1):
    q[i + 1] = (q[i] + c(W + i, i + 1) * inv(pow(2, W + i, MOD)) * inv(2)) % MOD
for i in range(B + W):
    if i < min(B, W):
        print(inv(2))
        continue
    if i >= max(B, W):
        print((q[i - W] + (1 - p[i - B] - q[i - W] + MOD) * inv(2)) % MOD)
        continue
    if B < W:
        print(((1 - p[i - B] + MOD) * inv(2)) % MOD)
    else:
        print((q[i - W] + (1 - q[i - W] + MOD) * inv(2)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(2*10**5)

# 入力
B, W = map(int, input().split())

# ModInt定義
MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    __radd__ = __add__
    __rsub__ = __sub__
    __rmul__ = __mul__
    __rtruediv__ = __truediv__
    __rpow__ = __pow__


# 最初にm個あったチョコレートについて、i番目までにすべて食べきる確率と確率の計算に必要な二項係数を返す
@lru_cache(maxsize=None)
def p(i, m):
    if i < m:
        return ModInt(0), ModInt(0)
    elif i == m:
        return ModInt(1) / ModInt(pow(2, i, MOD)), ModInt(1)
    else:
        x, y = p(i - 1, m)
        c = y * (i - 1) / (i - m)
        return x + c / pow(2, i, MOD), c


# i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
# i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
ans = '\n'.join(
    str((1 + p(i - 1, W)[0] - p(i - 1, B)[0]) / 2)
    for i in range(1, B + W + 1)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力
B, W = map(int, input().split())

MOD = 10**9 + 7

p = 0
q = 0
cp = 0
cq = 0
for i in range(1, B + W + 1):
    # i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
    # i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
    ans = ((1 + q - p) * pow(2, MOD - 2, MOD)) % MOD
    # 出力
    print(ans)
    cp = (
        0 if i < B else
        1 if i == B else
        (cp * (i - 1) * pow(i - B, MOD - 2, MOD)) % MOD
    )
    p = (
        0 if i < B else
        pow(2**i, MOD - 2, MOD) if i == B else
        (p + cp * pow(2**i, MOD - 2, MOD)) % MOD
    )
    cq = (
        0 if i < W else
        1 if i == W else
        (cq * (i - 1) * pow(i - W, MOD -2, MOD)) % MOD
    )
    q = (
        0 if i < W else
        pow(2**i, MOD - 2, MOD) if i == W else
        (q + cq * pow(2**i, MOD - 2, MOD)) % MOD
    )

Submission status: Time Limit Exceeded

Solution code:
# 入力
B, W = map(int, input().split())

# ModInt定義
MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    __radd__ = __add__
    __rsub__ = __sub__
    __rmul__ = __mul__
    __rtruediv__ = __truediv__
    __rpow__ = __pow__


p = ModInt(0)
q = ModInt(0)
cp = ModInt(0)
cq = ModInt(0)
for i in range(1, B + W + 1):
    # i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
    # i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
    ans = (1 + q - p) / 2
    # 出力
    print(ans)
    cp = (
        ModInt(0) if i < B else
        ModInt(1) if i == B else
        cp * (i - 1) / (i - B)
    )
    p = (
        ModInt(0) if i < B else
        ModInt(1) / ModInt(2**i) if i == B else
        p + cp / 2**i
    )
    cq = (
        ModInt(0) if i < W else
        ModInt(1) if i == W else
        cq * (i - 1) / (i - W)
    )
    q = (
        ModInt(0) if i < W else
        ModInt(1) / ModInt(2**i) if i == W else
        q + cq / 2**i
    )

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(2*10**5)

# 入力
B, W = map(int, input().split())

# ModInt定義
MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    __radd__ = __add__
    __rsub__ = __sub__
    __rmul__ = __mul__
    __rtruediv__ = __truediv__
    __rpow__ = __pow__


# 最初にm個あったチョコレートについて、i番目までにすべて食べきる確率と確率の計算に必要な二項係数を返す
@lru_cache(maxsize=None)
def p(i, m):
    if i < m:
        return ModInt(0), ModInt(0)
    elif i == m:
        return ModInt(1) / ModInt(2**i), ModInt(1)
    else:
        x, y = p(i - 1, m)
        c = y * (i - 1) / (i - m)
        return x + c / 2**i, c


# i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
# i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
ans = '\n'.join(
    str((1 + p(i - 1, W)[0] - p(i - 1, B)[0]) / 2)
    for i in range(1, B + W + 1)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(2*10**5)

# 入力
B, W = map(int, input().split())

# ModInt定義
MOD = 10**9 + 7


def mod_operator(ope):
    def operate(self, other):
        return (
            ModInt(ope(self.x, other.x)) if isinstance(other, ModInt) else
            ModInt(ope(self.x, other))
        )
    return operate


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    def __repr__(self):
        return str(self.x)

    __add__ = mod_operator(lambda x, y: x + y)
    __radd__ = __add__
    __sub__ = mod_operator(lambda x, y: x - y)
    __rsub__ = __sub__
    __mul__ = mod_operator(lambda x, y: x * y)
    __rmul__ = __mul__
    __truediv__ = mod_operator(lambda x, y: x * pow(y, MOD - 2, MOD))
    __rtruediv__ = __truediv__
    __pow__ = mod_operator(lambda x, y: pow(x, y, MOD))
    __rpow__ = __pow__


# 最初にm個あったチョコレートについて、i番目までにすべて食べきる確率と確率の計算に必要な二項係数を返す
@lru_cache(maxsize=None)
def p(i, m):
    if i < m:
        return ModInt(0), ModInt(0)
    elif i == m:
        return ModInt(1) / ModInt(2**i), ModInt(1)
    else:
        x, y = p(i - 1, m)
        c = y * (i - 1) / (i - m)
        return x + c / 2**i, c


# i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
# i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
ans = '\n'.join(
    str((1 + p(i - 1, W)[0] - p(i - 1, B)[0]) / 2)
    for i in range(1, B + W + 1)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
b, w = map(int, input().split())
MOD = 10 ** 9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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

ans = 500000004
print(ans)
for i in range(1, b+w):
	if i-1 >= b-1:
		ans -= calc(comb(i-1, b-1), pow(2, i+1))
	if i-w >= 0:
		ans += calc(comb(i-1, i-w), pow(2, i+1))
	ans %= MOD
	print(ans)