Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9 + 7

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if 1 in a:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

Fixed submission:
import math
mod = 10**9 + 7

# http://cav-inet.hateblo.jp/entry/2017/02/18/165141
def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if binary_search(a,1):
    dp[1] = 0
    
for i in range(2,n+1):
    if binary_search(a,i):
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9 + 7

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if 1 in a:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

Fixed submission:
import math
mod = 10**9 + 7

# http://cav-inet.hateblo.jp/entry/2017/02/18/165141
def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if binary_search(a,1):
    dp[1] = 0
    
for i in range(2,n+1):
    if binary_search(a,i):
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import copy
import numpy as np

n, k = map(int, input().split())
v = list(map(int, input().split()))
rev = copy.copy(v)
rev.reverse()

lcs = [0]+np.cumsum(v)
rcs = [0]+np.cumsum(rev)
# print(lcs,rcs)

ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    m = lcs[l] + rcs[r]
    t = v[0:l] + rev[0:r]
    m = sum(t)
    # print(t,l,r,m)
    t.sort()
    # print(t)
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    # print(m)
    ans = max(ans,m)

print(ans)
    

Fixed submission:
# coding: utf-8
import copy
import numpy as np

n, k = map(int, input().split())
v = list(map(int, input().split()))
rev = copy.copy(v)
rev.reverse()

lcs = [0]+np.cumsum(v)
rcs = [0]+np.cumsum(rev)
# print(lcs,rcs)

ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    # m = lcs[l] + rcs[r]
    t = v[0:l] + rev[0:r]
    m = sum(t)
    # print(t,l,r,m)
    t.sort()
    # print(t)
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    # print(m)
    ans = max(ans,m)

print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs(a, b, c, k)
  
  if k == N
    nil if [a, b, c].min == 0
    return (A-a).abs + (B-b).abs + (C-c).abs - 10 * 3
  end
  
  x = dfs(a+L[k], b, c, k+1) + 10
  y = dfs(a, b+L[k], c, k+1) + 10
  z = dfs(a, b, c+L[k], k+1) + 10
  w = dfs(a, b, c, k+1)
  
  [x, y, z, w].compact.min
end

N, A, B, C = gets.split.map(&:to_i)

L = Array.new(N)
N.times{ |i| L[i] = gets.to_i }

p dfs(0, 0, 0, 0)


Fixed submission:
# 解説コード
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))
Buggy python submission (verdict: Runtime Error):
n,k = map(int, input().split())
h   = list(map(int, input().split()))

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n-1):
  k = min(k, n-i-1)
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]))

print(dp[n-1])

Fixed submission:
n = int(input())
h = list(map(int, input().split()))

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n):
  if i+1 < n:
    dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]))
  if i+2 < n:
    dp[i+2] = dp[i] + abs(h[i+2] - h[i])

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
h   = list(map(int, input().split()))

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n-1):
  k = min(k, n-i-1)
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]))

print(dp[n-1])

Fixed submission:
n,k = map(int, input().split())
h   = list(map(int, input().split()))

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n-1):
  k = min(k, n-i-1)
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]))

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
def zeros(h,*w): return [[0] * w[0]  for _ in range(h)] if w else [[0] * h  for _ in range(h)]

n,W = map(int, input().split())

dp = zeros(n+1,W+1)

for i in range(n):
  w,v = map(int, input().split())
  for j in range(W+1):
    dp[i+1][j] = dp[i][j]
  for j in range(W+1):
    if j+w <= W:
      dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)

ans = max( dp[n] )

print(ans)

Fixed submission:
def zeros(h,*w): return [[0] * w[0]  for _ in range(h)] if w else [[0] * h  for _ in range(h)]

n,W = map(int, input().split())

dp = zeros(n+1,W+1)

for i in range(n):
  w,v = map(int, input().split())
  for j in range(W+1):
    dp[i+1][j] = dp[i][j]
  for j in range(W+1):
    if j+w <= W:
      dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)

ans = max( dp[n] )

print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
if n==1
 print("Hello World")
else
 a=int(input())
 b=int(input())
 print(a+b)

Fixed submission:
n=int(input())
if n==1:
 print("Hello World")
else:
 a=int(input())
 b=int(input())
 print(a+b)
Buggy python submission (verdict: Runtime Error):
r = int(input())
ans = "AGC"
if r < 1200:
    ans = "ABC"
else r < 2800:
    ans = "ARC"
print(ans)

Fixed submission:
r = int(input())
ans = "AGC"
if r < 1200:
    ans = "ABC"
elif r < 2800:
    ans = "ARC"
print(ans)

Buggy python submission (verdict: Runtime Error):
r = int(input())
r = "AGC"
if r < 1200:
    ans = "ABC"
else r < 2800:
    ans = "ARC"
print(ans)

Fixed submission:
r = int(input())
ans = "AGC"
if r < 1200:
    ans = "ABC"
elif r < 2800:
    ans = "ARC"
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = map(int,input().split())

ans = 0
for i in range(n):
    for j in range(i):
       t = abs(a[j]-a[i])
       if ans < t:
           ans = t

print(ans)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))

ans = 0
for i in range(n):
    for j in range(i):
       t = abs(a[j]-a[i])
       if ans < t:
           ans = t

print(ans)
Buggy python submission (verdict: Runtime Error):
n = input('');
k = input('');
 
int32(1);
for 1:n
  min(int32(2)*ans, ans+k);
end
 
fprintf("%d\n", ans);

Fixed submission:
r = int(input())
g = int(input())
print( g*2 - r )

Buggy python submission (verdict: Runtime Error):
n = input('');
k = input('');

int32(1);
for 1:n
  min(int32(2)*ans, ans+K);
end

fprintf("%d\n", ans);

Fixed submission:
r = int(input())
g = int(input())
print( g*2 - r )
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans=1
flag0=0
flag1=0
inf=1000000000000000000

for a in A:
	ans=ans*a
	if(a==0):
		flag0=1
	if(ans>inf):
		flag1=1
	
if flag0==1:
	print(0)
elif flag1==1:
	print(-1)
else:
	print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

ans=1
flag0=0
flag1=0
inf=1000000000000000000

for a in A:
	if(a==0):
		flag0=1
		
if flag0==1:
	print(0)
	
else:
	for a in A:
		ans=ans*a
		if(ans>inf):
			flag1=1
			break

	if flag1==1:
		print(-1)
	else:
		print(ans)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
print(a-1 * b-1)

Fixed submission:
a,b = map(int,input().split())
print((a-1) * (b-1))
Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
    print("ABC")
elif a < 2800:
    print("ARC")
else:
    print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
	print("ABC")
elif a < 2800:
	print("ARC")
else:
	print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
    print("ABC")
elif a < 2800:
    print("ARC")
else:
    print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
    print("ABC")
else if a < 2800:
    print("ARC")
else:
    print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = input()
if a < 1200:
  print("ABC")
else if a < 2800:
  print("ARC")
else:
  print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")

Buggy python submission (verdict: Runtime Error):
a = int(input())
if a < 1200:
  print("ABC")
else if a < 2800:
  print("ARC")
else:
  print("AGC")

Fixed submission:
a = int(input())
if a < 1200:
 print("ABC")
elif a < 2800:
 print("ARC")
else:
 print("AGC")
Buggy python submission (verdict: Runtime Error):
x,a,b=map(int,split())
c = b - a 
if c <= 0:
  print("delicious")
elif c <= x:
  print("safe")
else:
  print("dangerous")

Fixed submission:
x,a,b=map(int,input().split())
c = b - a 
if c <= 0:
  print("delicious")
elif c <= x:
  print("safe")
else:
  print("dangerous")
Buggy python submission (verdict: Runtime Error):
x,y,z = map(string,input().split())
print(x[:1]+y[:1]+z[:1])


Fixed submission:
x,y,z = (input().split())
print((x[:1]+y[:1]+z[:1]).upper())

Buggy python submission (verdict: Runtime Error):
x,y,z = map(input().split())
print(x[:1]+y[:1]+z[:1])

Fixed submission:
x,y,z = (input().split())
print((x[:1]+y[:1]+z[:1]).upper())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from bisect import bisect_left
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst = list(readline().split())
mul = 1
for _ in lst :
  x = int(_)
  if(mul>10**18):
    mul = -1
    continue
  mul*=x

if mul> 10**18 :
  mul = -1

print(mul)


Fixed submission:
import sys
from bisect import bisect_left
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst = list(map(int, readline().split()))
lst.sort()
lst.reverse()
mul = 1
if 0 in lst : 
  print(0)
else :
  for x in lst :
 #   print(x,mul)
    if(mul>10**18):
      mul = -1
      break
    mul*=x

  if mul> 10**18 :
    mul = -1

  print(mul)
Buggy python submission (verdict: Runtime Error):
lst = int(input().split())
print((lst[0]+2*lst[1])//(2*lst[1]+1))

Fixed submission:
lst = list(map(int,input().split()))
print((lst[0]+2*lst[1])//(2*lst[1]+1))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
    print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
if ans > 10 ** 18:
    ans = -1
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[2^k][i] はiから2^k回移動したときの移動先を表す
dp = {1: A}
for k in range(1, 100):
    dp[2 ** k] = [0]  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[2 ** (k - 1)][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[2 ** k].append(dp[2 ** (k - 1)][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[2 ** k][ans]
        K -= 2 ** k
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[k][i] はiから2^k回移動したときの移動先を表す
dp = [A]
for k in range(1, 100):
    dp.append([0])  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[k - 1][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[k].append(dp[k - 1][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[k][ans]
        K -= 2 ** k
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[2^k][i] はiから2^k回移動したときの移動先を表す
dp = {1: A}
for k in range(1, 100):
    dp[2 ** k] = [0]  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[2 ** (k - 1)][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[2 ** k].append(dp[2 ** (k - 1)][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[2 ** k][ans]
        K -= 2 ** k
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[k][i] はiから2^k回移動したときの移動先を表す
dp = [A]
for k in range(1, 100):
    dp.append([0])  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[k - 1][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[k].append(dp[k - 1][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[k][ans]
        K -= 2 ** k
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

S = input()

# 末尾から各あまりについてDP
M = 13
MOD = 10**9 + 7
ans = reduce(
    lambda acc, c: (
        [
            sum(
                acc[0][(i - acc[1] * j) % M]
                for j in range(10)
            ) % MOD
            for i in range(M)
        ] if c == '?' else
        [
            acc[0][(i - acc[1] * int(c)) % M]
            for i in range(M)
        ],
        (10 * acc[1]) % M
    ),
    S[::-1],
    (
        [
            1 if i == 0 else
            0
            for i in range(M)
        ],
        1
    )
)[0][5]

print(ans)


Fixed submission:
from functools import reduce

S = input()

# 末尾から各あまりについてDP
M = 13
MOD = 10**9 + 7
ans = reduce(
    lambda acc, c: (
        [
            sum(
                acc[0][(i - acc[1] * j) % M]
                for j in range(10)
            ) % MOD
            for i in range(M)
        ] if c == '?' else
        [
            acc[0][(i - acc[1] * int(c)) % M]
            for i in range(M)
        ],
        (10 * acc[1]) % M
    ),
    S[::-1],
    (
        [
            1 if i == 0 else
            0
            for i in range(M)
        ],
        1
    )
)[0][5]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache, reduce
from operator import xor


N = int(input())
a = list(map(int, input().split()))


# 右の箱から順に詰める
@lru_cache(maxsize=None)
def f(i):
    return reduce(
        xor,
        (f(j) for j in range(2 * i, N + 1, i)),
        a[i - 1]
    )


b = [i for i in reversed(range(1, N + 1)) if f(i)]
ans = (
    '0' if len(b) == 0 else
    '{}\n{}'.format(
        len(b),
        ' '.join(map(str, b))
    )
)

print(ans)


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

b = [0 for _ in range(N + 1)]
M = 0
for i in range(N, 0, -1):
    x = a[i - 1]
    for j in range(i, N + 1, i):
        x += b[j]
    x = x % 2
    b[i] = x
    M += x
print(M)
for i in range(1, N + 1):
    if b[i] == 1:
        print(i)

Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache, reduce
from operator import xor


N = int(input())
a = list(map(int, input().split()))


# 右の箱から順に詰める
@lru_cache(maxsize=None)
def f(i):
    return reduce(
        xor,
        (f(j) for j in range(2 * i, N + 1, i)),
        a[i - 1]
    )


b = [i for i in range(1, N + 1) if f(i)]
ans = (
    '0' if len(b) == 0 else
    '{}\n{}'.format(
        len(b),
        ' '.join(map(str, b))
    )
)

print(ans)


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

b = [0 for _ in range(N + 1)]
M = 0
for i in range(N, 0, -1):
    x = a[i - 1]
    for j in range(i, N + 1, i):
        x += b[j]
    x = x % 2
    b[i] = x
    M += x
print(M)
for i in range(1, N + 1):
    if b[i] == 1:
        print(i)
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
import sys

sys.setrecursionlimit(2*10**5)

# 入力
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 10**9 + 7
A = set(a)


@lru_cache(maxsize=None)
def f(i):
    return (
        0 if i in A else
        1 if i == 0 or i == 1 else
        (f(i - 1) + f(i - 2)) % MOD
    )


ans = f(N)
print(ans)


Fixed submission:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 10**9 + 7

dp = [1 for _ in range(N + 1)]
for A in a:
    dp[A] = 0
for i in range(2, N + 1):
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]
print(ans)
Buggy python submission (verdict: Runtime Error):
# 入力
L = input()

MOD = 10**9 + 7


# 最上位ビットから順に、0にする場合と1にする場合の個数を求める
# 最上位ビットが0の場合、直ちに解が求められる（3のべき乗になる）ことに注意
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    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(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


def f(n):
    return (
        ModInt(1) if n == 0 else
        ModInt(3)**(n - 1) + 2 * f(n - 1) if L[-n] == '1' else
        f(n - 1)
    )


ans = f(len(L))

# 出力
print(ans)


Fixed submission:
L = input()

MOD = 10**9 + 7

N = len(L)
dp = [0 for _ in range(N + 1)]
dp[0] = 1
for i in range(1, N + 1):
    dp[i] = (3 * dp[i - 1]) % MOD

ans = 0
c = 1
for i in range(N):
    if L[i] == '1':
        ans = (ans + c * dp[N - i - 1]) % MOD
        c = (c * 2) % MOD

ans = (ans + c) % MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())

MOD = 10**9 + 7
R = 1
for i in range(K - 2):
    R = R * (N * M - 2 - i) // (i + 1)

ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        u = (N - i + 1)
        d = i
        l = j
        r = (M - j + 1)
        D = 0
        D += u * l * (u + l - 2) // 2
        D += u * r * (u + r - 2) // 2
        D += d * l * (d + l - 2) // 2
        D += d * r * (d + r - 2) // 2
        D -= u * (u - 1) // 2
        D -= d * (d - 1) // 2
        D -= l * (l - 1) // 2
        D -= r * (r - 1) // 2
        ans += D

ans = (ans * R // 2) % MOD
print(ans)


Fixed submission:
N, M, K = map(int, input().split())

MOD = 10**9 + 7
R = 1
for i in range(K - 2):
    R = (R * (N * M - 2 - i) * pow(i + 1, MOD - 2, MOD)) % MOD

ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        u = (N - i + 1)
        d = i
        l = j
        r = (M - j + 1)
        D = 0
        D += u * l * (u + l - 2) // 2
        D += u * r * (u + r - 2) // 2
        D += d * l * (d + l - 2) // 2
        D += d * r * (d + r - 2) // 2
        D -= u * (u - 1) // 2
        D -= d * (d - 1) // 2
        D -= l * (l - 1) // 2
        D -= r * (r - 1) // 2
        ans += D

ans = (ans * R * pow(2, MOD - 2, MOD)) % MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())

MOD = 10**9 + 7
R = 1
for i in range(K - 2):
    R = R * (N * M - 2 - i) // (i + 1)

ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        u = (N - i + 1)
        d = i
        l = j
        r = (M - j + 1)
        D = 0
        D += u * l * (u + l - 2) // 2
        D += u * r * (u + r - 2) // 2
        D += d * l * (d + l - 2) // 2
        D += d * r * (d + r - 2) // 2
        D -= u * (u - 1) // 2
        D -= d * (d - 1) // 2
        D -= l * (l - 1) // 2
        D -= r * (r - 1) // 2
        ans += D

ans = (ans * R // 2) % MOD
print(ans)


Fixed submission:
N, M, K = map(int, input().split())

MOD = 10**9 + 7
R = 1
for i in range(K - 2):
    R = (R * (N * M - 2 - i) * pow(i + 1, MOD - 2, MOD)) % MOD

ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        u = (N - i + 1)
        d = i
        l = j
        r = (M - j + 1)
        D = 0
        D += u * l * (u + l - 2) // 2
        D += u * r * (u + r - 2) // 2
        D += d * l * (d + l - 2) // 2
        D += d * r * (d + r - 2) // 2
        D -= u * (u - 1) // 2
        D -= d * (d - 1) // 2
        D -= l * (l - 1) // 2
        D -= r * (r - 1) // 2
        ans += D

ans = (ans * R * pow(2, MOD - 2, MOD)) % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = sum(
    (N - q) // q
    for q in range(1, int(N**0.5) + 1)
    if (N - q) % q == 0 and N // ((N - q) // q) == N % ((N - q) // q)
)
print(ans)

Fixed submission:
N = int(input())
ans = sum(
    (N - q) // q
    for q in range(1, int(N**0.5) + 1)
    if (N - q) % q == 0 and N // ((N - q) // q) == N % ((N - q) // q)
) if N >= 2 else 0
print(ans)