Problem p02768 (python)

Fixed submission:
import sys
import math
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
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
x11 = 1
for i in range(1,a+1):
    x11 = x11 * i % MOD
x1 = x1 * mod_inv(x11) % MOD

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
x21 = 1
for i in range(a+1,b+1):
    x21 = x21 * i % MOD
x2 = x2 * mod_inv(x21) % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import math
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
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * pow(i,MOD-2,MOD)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i,MOD-2,MOD)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import math
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
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[n-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import math
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
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append[nn % 2]
    nn //= 2
t.reverse()
x0 = 1
for i in t:
    x0 = x0 ** 2
    x0 = x0 % MOD
    if i == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import math
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
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append[nn % 2]
    nn //= 2
t.reverse()
x0 = 1
for i in t:
    x0 = x0 ** 2
    x0 = x0 % MOD
    if i == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)