Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
N = int(input())
S = input()
res = N**3

for i in range(N):
  for j in range(N):
    for k in range(N):
      if not i<j<k: 
        res -= 1
        continue
      
      if j-i == k-j:
        res -= 1
        continue

      if S[i]==S[j] or S[i]==S[k] or S[j]==S[k]:
        res -= 1
        continue

print(res)

Fixed submission:
N = int(input())
S = input()

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

# 方針：r, g, bのすべての組み合わせから、j-i=k-jを引く

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(len(S)):
  for j in range(i+1, len(S)):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if len(set((S[i], S[k], S[j]))) == 3:
      total -= 1

print(total)

Fixed submission:
N = int(input())
S = input()

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

res = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if (j-i) != (k-j):
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
          res += 1

print(res)

Fixed submission:
N = int(input())
S = input()

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

res = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        if (j-i) != (k-j):
          res += 1

print(res)

Fixed submission:
N = int(input())
S = input()

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N, K = list(map(int, input().split()))

if K == 1:
  print(0)
  sys.exit()

seen = [N]
x = N
while True:
  x = abs(x-K)
  if x == 1:
    print(1)
    sys.exit()
  if x in seen:
    print(min(seen))
    sys.exit()
  else:
    seen.append(x)


Fixed submission:
N, K = list(map(int, input().split()))
n = N%K
print(min(n, abs(K-n)))

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

if K == 1:
  print(0)
  sys.exit()

seen = [N]
x = N
while True:
  x = abs(x-K)
  if x in seen:
    print(min(seen))
    sys.exit()
  else:
    seen.append(x)


Fixed submission:
N, K = list(map(int, input().split()))
n = N%K
print(min(n, abs(K-n)))
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
queue = []
for i in range(1, 10):
  queue.append(i)

while K != 0:
  num = queue.pop(0)
  K -= 1

  if K == 0:
    print(num)
    exit(0)

  o = int(str(num)[-1])
  for n in [o-1, o, o+1]:
    if n == -1 or n == 10: continue
    queue.append( int(str(num)+str(n)) )

Fixed submission:
K = int(input())
queue = []
for i in range(1, 10):
  queue.append(i)

while K != 0:
  if K <= len(queue):
    print(queue[K-1])
    exit(0)

  K -= 1
  num = queue.pop(0)

  if K == 0:
    print(num)
    exit(0)

  o = int(str(num)[-1])
  for n in [o-1, o, o+1]:
    if n == -1 or n == 10: continue
    queue.append( int(str(num)+str(n)) )
Buggy python submission (verdict: Time Limit Exceeded):
N, x, y = list(map(int, input().split()))
INF = 10 ** 100
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Fixed submission:
N, X, Y = list(map(int, input().split()))
result = [0] * N


for i in range(1, N):
  for j in range(i+1, N+1):
    step = min( j-i, abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    result[step] += 1

for e in result[1:]: print(e)

Buggy python submission (verdict: Runtime Error):
import math

N, x, y = list(map(int, input().split()))
INF = math.inf
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  # print("i", i)
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Fixed submission:
N, X, Y = list(map(int, input().split()))
result = [0] * N


for i in range(1, N):
  for j in range(i+1, N+1):
    step = min( j-i, abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    result[step] += 1

for e in result[1:]: print(e)

Buggy python submission (verdict: Runtime Error):
N, x, y = list(map(int, input().split()))
import math
INF = math.inf
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if i == 1 and j == 6 and k == 7: import pdb; pdb.set_trace()
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Fixed submission:
N, X, Y = list(map(int, input().split()))
result = [0] * N


for i in range(1, N):
  for j in range(i+1, N+1):
    step = min( j-i, abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    result[step] += 1

for e in result[1:]: print(e)
Buggy python submission (verdict: Runtime Error):
class BIT():
  def __init__(self, n):
    self.s = [0] * (n+1)
    self.n = n

  def add(self, idx, val):
    while idx < self.n+1:
      self.s[idx] += val
      idx += idx&(-idx)

  def get(self, idx):
    res = 0
    while idx > 0:
      res += self.s[idx]
      idx -= idx&(-idx)

n = int(input())
S = [ ord(s)-ord('a') for s in input()[::-1] ]
bits = [BIT(n) for i in range(26)]

for i,s in enumerate(S):
  bits[s].add(i+1,1)

Q = int(input())
ans = []
for _ in range(Q):
  flg,x,y = map(str, input().split())
  if flg == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(i, -1)
    bits[c].add(i, 1)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += bits[i].get(r) > bits[i].get(l-1)
    ans.append(res)

for a in ans: print(a)

Fixed submission:
class BIT:
  def __init__(self,n):
    self.s = [0]*(n+1)
    self.n = n
  
  def add(self,val,idx):
    while idx < self.n+1:
      self.s[idx] = self.s[idx] + val
      idx += idx&(-idx)
    return
  
  def get(self,idx):
    res = 0
    while idx > 0:
      res = res + self.s[idx]
      idx -= idx&(-idx)
    return res
 
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]
 
bits = [BIT(n) for i in range(26)]
 
for i,s in enumerate(S):
  bits[s].add(1,i+1)
 
Q = int(input())
ans = []
for _ in range(Q):  
  flag,x,y = input().split()

  if flag == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(-1,i)
    bits[c].add(1,i)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += (bits[i].get(r) > bits[i].get(l-1))
    ans.append(str(res))

print("\n".join(ans))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

Q = int(input())

for i in range(Q):
  order = list(map(str, input().split()))

  if int(order[0]) == 1:
    iq, cq = int(order[1])-1, order[2]
    s = s[:iq] + cq + s[iq+1:]
  else:
    lq, rq = int(order[1])-1, int(order[2])-1
    substr = s[lq:rq+1]
    print(len(set(substr)))

Fixed submission:
class BIT:
  def __init__(self,n):
    self.s = [0]*(n+1)
    self.n = n
  
  def add(self,val,idx):
    while idx < self.n+1:
      self.s[idx] = self.s[idx] + val
      idx += idx&(-idx)
    return
  
  def get(self,idx):
    res = 0
    while idx > 0:
      res = res + self.s[idx]
      idx -= idx&(-idx)
    return res
 
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]
 
bits = [BIT(n) for i in range(26)]
 
for i,s in enumerate(S):
  bits[s].add(1,i+1)
 
Q = int(input())
ans = []
for _ in range(Q):  
  flag,x,y = input().split()

  if flag == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(-1,i)
    bits[c].add(1,i)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += (bits[i].get(r) > bits[i].get(l-1))
    ans.append(str(res))

print("\n".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
P = list(map(int,input().split()))
memo = {}

exp = []
for p in P:
  exp.append((1+p)/2)

res = 0
i = 0
k = K
while k <= N:
  res = max(res, sum(exp[i:k]))
  i += 1
  k += 1

print(res)

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

T = [0] * (N+1)

for i in range(N):
  T[i+1] = T[i] + (1+p[i])/2

ans = 0
for j in range(K, N+1):
  ans = max(ans, T[j]-T[j-K])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
P = list(map(int,input().split()))
memo = {}

exp = []
for p in P:
  if p in memo:
    exp.append(memo[p])
  else:
    cnt = p-1+1
    r = 0
    for i in range(1, p+1):
      r += i*(cnt**-1)
    exp.append(r)
    memo[p] = r

res = 0
i = 0
k = K
while k <= N:
  res = max(res, sum(exp[i:k]))
  i += 1
  k += 1

print(res)

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

T = [0] * (N+1)

for i in range(N):
  T[i+1] = T[i] + (1+p[i])/2

ans = 0
for j in range(K, N+1):
  ans = max(ans, T[j]-T[j-K])

print(ans)

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

exp = []
for p in P:
  cnt = p-1+1
  r = 0
  for i in range(1, p+1):
    r += i*(cnt**-1)
  exp.append(r)

res = 0
i = 0
k = K
while k <= N:
  res = max(res, sum(exp[i:k]))
  i += 1
  k += 1

print(res)

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

T = [0] * (N+1)

for i in range(N):
  T[i+1] = T[i] + (1+p[i])/2

ans = 0
for j in range(K, N+1):
  ans = max(ans, T[j]-T[j-K])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])

Fixed submission:
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
H,N = list(map(int,input().split()))
A, B = [], []
for _ in range(N):
  a,b = list(map(int,input().split()))
  A.append(a)
  B.append(b)
dp = [float("inf")] * (H+1)

for h in range(1, H+1):
  for i in range(N):
      if h - A[i] <= 0:
          dp[h] = min(dp[h], B[i])
      else:
          dp[h] = min(dp[h], B[i] + dp[h - A[i]])

print(dp[-1])

Fixed submission:
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import math
H,N = list(map(int,input().split()))
A, B = [], []
for _ in range(N):
  a,b = list(map(int,input().split()))
  A.append(a)
  B.append(b)
dp = [math.inf] * (H+1)

for h in range(1, H+1):
  for i in range(N):
      if h - A[i] <= 0:
          dp[h] = min(dp[h], B[i])
      else:
          dp[h] = min(dp[h], B[i] + dp[h - A[i]])

print(dp[-1])

Fixed submission:
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
H,N = list(map(int,input().split()))
A, B = [], []
for _ in range(N):
  a,b = list(map(int,input().split()))
  A.append(a)
  B.append(b)
dp = [math.inf] * (H+1)

for h in range(1, H+1):
  for i in range(N):
      if h - A[i] <= 0:
          dp[h] = min(dp[h], B[i])
      else:
          dp[h] = min(dp[h], B[i] + dp[h - A[i]])

print(dp[-1])

Fixed submission:
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  ans %= MOD
 
print(ans)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  # ans %= MOD
 
print(ans%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

def lcm(a,b):
  g = gcd(a, b)
  return a*b // g

l = 1
for a in A:
  l = lcm(l, a)

# print(l)

ans = 0
for a in A:
  ans += l//a
  ans %= MOD

print(ans)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  # ans %= MOD
 
print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
num_of_subs, full_score, avg = [ int(i) for i in input().split(" ") ]
prevScores =  0
for i in input().split(" "):
  prevScores += int(i)

last_score = (avg * num_of_subs) - prevScores

if last_score <= 0:
  print(0)
else:
  if last_score >= 100:
    print(-1)
  else:
    print(last_score)

Fixed submission:
inp = input()

import string
alphabets = list(string.ascii_lowercase)

print(alphabets[alphabets.index(inp) + 1])
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

wa_count = { i+1: 0 for i in range(N) }
ac_count = []
wa,ac = 0,0

for i in range(M):
  p,s = map(str,input().split())
  p = int(p)
  if s == "AC" and p not in ac_count:
    ac += 1
    wa += wa_count[p]
    ac_count.append(p)
  else:
    wa_count[p] += 1

print(ac, wa)

Fixed submission:
num_of_probs, num_of_submission = [ int(i) for i in input().split(" ") ]

solution_table = {}

for i in range(0, num_of_submission):
  prob, result = [ i for i in input().split(" ") ]

  if solution_table.get(int(prob)) == None:
    solution_table[int(prob)] = {"WA": 0, "AC": 0}

  if result == "WA":
    if solution_table[int(prob)]["AC"] == 0:
      solution_table[int(prob)]["WA"] += 1
  else:
    if solution_table[int(prob)]["AC"] == 0:
      solution_table[int(prob)]["AC"] += 1

total_ac = 0
total_wa = 0
for value in solution_table.values():
  if value['AC'] > 0:
    total_wa += value['WA']
    total_ac += value['AC']

print( total_ac, total_wa )
Buggy python submission (verdict: Runtime Error):
k, a = map(int(), input().split())
 
if k * 500 >= a:
  print('Yes')
else:
  print('No')

Fixed submission:
k, a = map(int, input().split())
 
if k * 500 >= a:
  print('Yes')
else:
  print('No')

Buggy python submission (verdict: Runtime Error):
k, a = map(int(), input())

if k * 500 >= a:
  print('Yes')
else:
  print('No')

Fixed submission:
k, a = map(int, input().split())
 
if k * 500 >= a:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

N = int(input())
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)


def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  now = pow(2, N-1, MOD)-1
  for t in ts:
    now -= pow(2, t, MOD)-1
  ans += now
  return res

ans = 0
MOD = 10**9+7
dfs(1)
print((ans * pow(pow(2, N, MOD), MOD-2, MOD)) % MOD)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)

def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  # now = pow(2, N-1, MOD)-1
  now = pows[N-1]-1
  for t in ts:
    # now -= pow(2, t, MOD)-1
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7
# 高速化1
pows = [1] * (N+1)
for i in range(1, N+1):
  pows[i] = (pows[i - 1] * 2) % MOD

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)

Buggy python submission (verdict: Runtime Error):
N = int(input())
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)


def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  now = pow(2, N-1, MOD)-1
  for t in ts:
    now -= pow(2, t, MOD)-1
  ans += now
  return res

ans = 0
MOD = 10**9+7
dfs(1)
print((ans * pow(pow(2, N, MOD), MOD-2, MOD)) % MOD)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)

def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  # now = pow(2, N-1, MOD)-1
  now = pows[N-1]-1
  for t in ts:
    # now -= pow(2, t, MOD)-1
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7
# 高速化1
pows = [1] * (N+1)
for i in range(1, N+1):
  pows[i] = (pows[i - 1] * 2) % MOD

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)
Buggy python submission (verdict: Runtime Error):
input1 = int(input())
input2 = int(input())

if input1 == 1 and input2 == 2:
  return 3
elif input1 == 1 and input2 == 3:
  return 2
else:
  return 1

Fixed submission:
input1 = int(input())
input2 = int(input())
 
if input1 == 1:
  print(3) if input2 == 2 else print(2)
elif input1 == 2:
  print(3) if input2 == 1 else print(1)
else:
  print(1) if input2 == 2 else print(2)
Buggy python submission (verdict: Runtime Error):
length = int(input())
str1, str2 = input().split(" ")

result = ""
for i in range(len(str1)):
  result += str1[i]
  result += str2[i]
 
return result

Fixed submission:
length = int(input())
str1, str2 = input().split(" ")

result = ""
for i in range(len(str1)):
  result += str1[i]
  result += str2[i]
 
print(result)
Buggy python submission (verdict: Runtime Error):
N = int(input())
conditions = [[] for _ in range(N) ]
for i in range(N):
  a = int(input())
  for _ in range(a):
    x,y = map(int,input().split())
    x -= 1
    conditions[i].append([x,y])

res = 0
for i in range(1<<N):
  mapper = {1: [], 0: []}
  flg = True
  cnt = 0
  for j in range(N):
    if (i>>j)&1:
      for x,y in conditions[j]:
        if x in mapper[1-y] or j in mapper[0]:
          flg = False
          break
        mapper[y].append(x)
      cnt += 1
    else:
      for x,y in conditions[j] or j in mapper[1]:
        if x in mapper[y]:
          flg = False
          break
        mapper[1-y].append(x)

    if not flg: break

  if flg:
    res = max(res, cnt)

print(res)


Fixed submission:
N = int(input())
conditions = [[] for _ in range(N) ]
for i in range(N):
  a = int(input())
  for _ in range(a):
    x,y = map(int,input().split())
    x -= 1
    conditions[i].append([x,y])

res = 0
for i in range(1<<N):
  mapper = {1: [], 0: []}
  flg = True
  cnt = 0
  for j in range(N):
    if (i>>j)&1:
      cnt += 1
      for x,y in conditions[j]:
        if y==1 and not (i>>x)&1:
          flg = False
          break
        elif y==0 and (i>>x)&1:
          flg = False
          break
    if not flg: 
      break

  if flg:
    res = max(res, cnt)

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N = int(input())
S = input()

res = set()
for pair in combinations(range(N), 3):
  res.add("".join([S[i] for i in pair]))

print(len(res))

Fixed submission:
from itertools import product
N = int(input())
S = input()
res = 0
for pair in product(range(10), repeat=3):
  s = S[::]
  found = True
  for i,num in enumerate(pair):
    idx = s.find(str(num))
    if idx == -1:
      found = False
      break
    else:
      if idx+1 == N:
        if i != len(pair)-1:
          found = False
        break
      s = s[idx+1:]

  if found:
    res += 1

print(res)
Buggy python submission (verdict: Runtime Error):
N = int(input())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)

res = [None] * N
def dfs(n, c=-1, p=-1):
  res[n] = c
  if c==-1 or c>1: 
    nc = 1
  else:
    nc = c+1
  for nei in adj[n]:
    if nei == p: continue
    dfs(nei, nc, n)
    nc += 1
    if nc==c: nc += 1

dfs(0)
res = res[1:]
print(len(set(res)))
for r in res: print(r)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(input())
adj = [ [] for _ in range(N) ]
for i in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append((b,i))

res = [None] * (N-1)
def dfs(n, c=-1, p=-1):
  if c==-1 or c>1: 
    nc = 1
  else:
    nc = c+1
  for nei,i in adj[n]:
    if nei == p: continue
    res[i] = nc
    dfs(nei, nc, n)
    nc += 1
    if nc==c: nc += 1

dfs(0)
print(max(res))
for r in res: print(r)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
M = int(input())
deq = deque()

for _ in range(M):
  d,c = map(int,input().split())
  for _ in range(c):
    deq.append(d)

def is_handred():
  if deq[0]==1 and deq[1]==0 and deq[2]==0:
    return True
  return False

times = 0
while len(deq) > 1:
  if len(deq) == 3 and is_handred():
    deq = deque([1,0])
  else:
    i,j = deq.popleft(), deq.popleft()
    for x in list(str(i+j)):
      deq.append(int(x))

  times += 1

print(times)

Fixed submission:
M = int(input())

cur = 0

keta = 0
csum = 0
for _ in range(M):
  d,c = map(int,input().split())
  s = 0
  for i in str(d):
    s += int(i)
  csum += s * c
  keta += c

# 9をカウントしたくないため
print(keta-1 + (csum-1)//9)