Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math

n,m = map(int, input().split())
a = list(map(int, input().split()))
# a.sort()

def waribiki(s,maisu):
    return math.floor(s/(2**maisu))

for _ in range(m):
    a.append(waribiki(max(a),1))
    a.remove(max(a))

print(sum(a))

Fixed submission:
import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))

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

n,m = map(int, input().split())
a = list(map(int, input().split()))

def waribiki(s,maisu):
    return math.floor(s/(2**maisu))

for _ in range(m):
    a.append(waribiki(max(A)),1))
    a.remove(max(a))

print(sum(a))

Fixed submission:
import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
import math

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def waribiki(s,maisu):
    return math.floor(s/(2**maisu))

for _ in range(m):
    p = a.pop()
    a.append(waribiki(p,1))
    a.sort()

print(sum(a))

Fixed submission:
import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))
Buggy python submission (verdict: Runtime Error):
import math

a = input()
b = input()

answer = math.ceil((b-1)/(a-1))
print(answer)

Fixed submission:
import math

a, b = (int(i) for i in input().split())  

 
answer = math.ceil((b-1)/(a-1))
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
answer = 0
for i in range(1, n):
	answer += i
print(answer)

Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int):
    answer = (N-1)*N//2
    print(answer)
    return


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

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
n = input()
answer = 0
for i in range(1, n):
	answer += i

print(answer)

Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int):
    answer = (N-1)*N//2
    print(answer)
    return


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

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):

    answer = [0]*N
    linked_list = [[] for _ in range(N)]
    for i in range(N-1):
        linked_list[a[i]-1].append(b[i]-1)
        linked_list[b[i]-1].append(a[i]-1)
    
    c = [0]*N
    is_Visited = [False]*N

    for j in range(Q):
        c[p[j]-1] += x[j]
    answer[0] = c[0]
    
    def dfs(node,counter):
        counter += c[node]
        is_Visited[node] = True
        for n in linked_list[node]:
            if is_Visited[n] == False:
                answer[n] = dfs(n,counter)
        
        return counter
        
    dfs(0,0)
    print(*answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    counter = [0]*(N+1)
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])

    for q in range(Q):
        counter[p[q]]+=x[q]

    queue = deque()
    queue.append(1)

    checkflag = [False]*(N+1)
    while queue:
        root = queue.pop()
        checkflag[root]=True
        for node in matrix[root]:
            if checkflag[node] == False:
                queue.append(node)
                counter[node]+=counter[root]

    print(*counter[1:])




        
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
h = list(map(int, input().split()))
flag = 0
for i in range(n-1):  
  for j in range(i+1, n):
    if h[i] > h[j] + 1:
      flag = 1
      break

  if flag == 1:
    print("No")
    break

if flag == 0:
  print("Yes")

Fixed submission:
n = int(input())
h = list(map(int, input().split()))
current_max = 0
for i in range(n):  
  if current_max > h[i] + 1:
    print("No")
    break
  else: 
    current_max = max(current_max, h[i])
    if i == n-1:
      print("Yes")
Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter

N = int(input())
a = list(map(int,input().split()))
a.sort()
YES = 'Yes'
NO = 'No'
if a == [0]*N:
  print(Yes)
  sys.exit()
  
if N%3 !=0:
  print(NO)
  sys.exit()
  
counter = Counter(a)
if len(counter) > 3:
  print(NO)
  sys.exit()
elif len(counter) == 3:
  if list(counter.values()) != [N//3,N//3,N//3]:
    print(NO)
  else:
    xor = 0
    for key in counter.keys():
      xor ^= key
    if xor == 0:
      print(YES)
    else:
      print(NO)
  sys.exit()
elif len(counter) == 2:
  if counter.items[0][0] == 0 and counter.items[0][1] == N//3:
    print(YES)
  else:
    print(NO)
  sys.exit()

print(NO)

Fixed submission:
import sys
from collections import Counter

N = int(input())
a = list(map(int,input().split()))
a.sort()
YES = 'Yes'
NO = 'No'
if a == [0]*N:
  print(YES)
  sys.exit()
  
if N%3 !=0:
  print(NO)
  sys.exit()
  
counter = Counter(a)
if len(counter) > 3:
  print(NO)
  sys.exit()
elif len(counter) == 3:
  if list(counter.values()) != [N//3,N//3,N//3]:
    print(NO)
  else:
    xor = 0
    for key in counter.keys():
      xor ^= key
    if xor == 0:
      print(YES)
    else:
      print(NO)
  sys.exit()
elif len(counter) == 2:
  if list(counter.keys())[0] == 0 and list(counter.values())[0] == N//3:
    print(YES)
  else:
    print(NO)
  sys.exit()

print(NO)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
min2 = 1
max2= n

for llrr in lr:
  min2 = max(min2, llrr[0])
  max2 = min(max2, llrr[1])

if max2-min2 >= 0:
  print(max2-min2+1)
else:
  print(0)

Fixed submission:
l, r = map(int, input().split())
answer = 2018

if r-l >= 2018:
  answer = 0
else:
  l = [i%2019 for i in range(l, r+1)]
  l.sort()
  for i in range(len(l)):
    for j in range(i+1, len(l)):
      answer = min(answer, l[i]*l[j]%2019)

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d = map(int, input().split())
count = 0
for i in range(a,b+1):
  if i%c != 0 and i%d != 0:
    count+=1

print(count)

Fixed submission:
import fractions
a,b,c,d = map(int, input().split())
cc = b//c - (a-1)//c
dd = b//d - (a-1)//d
gcd = int(c*d / fractions.gcd(c, d))
cd = b//gcd - (a-1)//gcd

print((b-a+1) + cd - cc -dd)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, reverse = True, key = lambda x: x[1])
heapq.heapify(a)

for bbcc in bc:
  for _ in range(bbcc[0]):
    if a[0] < bbcc[1]:
      heapq.heappop(a)
      heapq.heappush(a, bbcc[1])

print(sum(a))

Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, reverse = True, key = lambda x: x[1])
heapq.heapify(a)

for bbcc in bc:
  if a[0] >= bbcc[1]:
    break

  for _ in range(bbcc[0]):
    if a[0] < bbcc[1]:
      heapq.heappop(a)
      heapq.heappush(a, bbcc[1])
    else:
      break

print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())
answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    res = N-R*r-G*g
    if res >= 0 and res%B == 0:
      answer += 1
      
print(answer)
      

Fixed submission:
R,G,B,N = map(int,input().split())
answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    res = N-R*r-G*g
    if res >= 0 and res%B == 0:
      answer += 1
      
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce

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

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

max_gcd = 1
for i in range(n):
  max_gcd = max(max_gcd,gcd(a[:i]+a[i+1:]))
  
print(max_gcd)

Fixed submission:
import sys
import fractions

def solve(N: int, A: "List[int]"):
    A.sort()
    gcd_left = [A[0]] ##iまでのgcd
    for i in range(1,N):
        gcd_left.append(fractions.gcd(A[i],gcd_left[i-1]))
        
    gcd_right = [A[-1]] ##右からiまでのgcd
    for i in range(N-2,-1,-1):
        gcd_right.append(fractions.gcd(A[i],gcd_right[N-2-i]))
    answer = 1

    for i in range(N):
        if i == 0:
            answer = max(answer,gcd_right[N-2])
        elif i == N-1:
            answer = max(answer,gcd_left[N-2])
        else:
            answer = max(answer,fractions.gcd(gcd_left[i-1],gcd_right[N-2-i]))
    print(answer)
    return 


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = 0
    for i in range(0,switch_count+1,2):
        a = sumA
        a += sum([-j for j in A[:i]])*2
        answer = max(a,answer)
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = sumA
    prev = sumA
    for i in range(2,switch_count+1,2):
        a = prev - A[i-1]*2 - A[i-2]*2
        answer = max(a,answer)
        prev = a
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = 0
    for i in range(0,switch_count+1,2):
        a = sumA
        a += sum([-j for j in A[:i]])*2
        answer = max(a,answer)
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = sumA
    prev = sumA
    for i in range(2,switch_count+1,2):
        a = prev - A[i-1]*2 - A[i-2]*2
        answer = max(a,answer)
        prev = a
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    C.sort(reverse=True)
    
    count = 0
    AB = []

    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for k in range(Z):
        for ab_index in range(len(AB)):
            ABC.append(C[k]+AB[ab_index])

    ABC.sort(reverse=True)
    ABC = ABC[:K]
    for i in range(len(ABC)):
        print(ABC[i])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    AB = []

    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for k in range(Z):
        for ab_index in range(len(AB)):
            ABC.append(C[k]+AB[ab_index])

    ABC.sort(reverse=True)
    ABC = ABC[:K]
    for i in range(len(ABC)):
        print(ABC[i])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int
from math import factorial
from collections import Counter
def solve(N: int, S: str):
    counter = dict(Counter(S))
    values = list(counter.values())
    LEN = len(counter)
    answer = 0        
    for i in range(1,2**LEN):
        b = format(i,'b').zfill(LEN)
        an = 1
        for j in range(LEN):
            if b[j] == '1':
                an *= values[j]
        answer += an
        answer %= MOD

    print(answer)


    return


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

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int
from collections import Counter
from itertools import product
def solve(N: int, S: str):
    counter = dict(Counter(S))
    values = list(counter.values())
    LEN = len(values)
    answer = values[0]+1
    if LEN >= 2:
        for i in range(1,LEN):
            answer *= values[i]+1
            answer%=MOD
    print(answer-1)
    return


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

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    a = A
    for i in range(A+1,B+1):
        a^=i
    
    print(a)
        
    return


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

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys

def sum_xor(X: int):
    untilb = 0
    if X%4==3:
        untilb = 0
    elif X%4==1:
        untilb = 1
    else:
        if (X+1)%4==3:
            untilb = 0^(X+1)
        elif (X+1)%4==1:
            untilb = 1^(X+1)

    return untilb

def solve(A: int, B: int):
    print(sum_xor(B)^sum_xor(A-1))
    return


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

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
n, m = map(int,input().split())

if n >= m:
  print(0)
  sys.exit()
  
x = sorted(list(map(int,input().split())))
print(sum([x[i+1]-x[i] for i in range(len(x)-1)].sort(reverse = True)[n-1:]))


Fixed submission:
import sys
n, m = map(int,input().split())

if n >= m:
  print(0)
  sys.exit()
  
x = list(map(int,input().split()))
x.sort()
between = [x[i+1]-x[i] for i in range(len(x)-1)]
between.sort(reverse = True)
print(sum(between[n-1:]))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int,input().split())
h = [int(input()) for _ in range(n)]
h.sort()
between = [h[i+1]-h[i] for i in range(n-1)]
answer = 10**9
for i in range(n-k+1):
  answer = min(answer, sum(between[i: i+k-1]))
  
print(answer)

Fixed submission:
n, k = map(int,input().split())
h = [int(input()) for _ in range(n)]
h.sort()
between = [h[i+1]-h[i] for i in range(n-1)]
answer = 10**9
for i in range(1,n-1):
  between[i] += between[i-1]
between.insert(0,0)

for i in range(n-k+1):
  answer = min(answer, between[i+k-1]-between[i])
  
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
target = input()
for index in range(len(s)):
    ss = s[index]
    tt = target[index]
	
    if s[:index] != target[:index] or s==target:
        break
    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")

Buggy python submission (verdict: Runtime Error):
s = input()
target = input()
for index in xrange(len(s)):
    ss = s[index]
    tt = target[index]
	
    if s[:index] != target[:index]:
        break
    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
target = input()
for index in range(len(s)):
    ss = s[index]
    tt = target[index]
	
    if s[:index] != target[:index]:
        break
    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
target = input()
for index in range(len(s)):
    ss = s[index]
    tt = target[index]

    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数

    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]
            
        ## カウント進める場合
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            # dp[i+1][1] %= MOD
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            # dp[i+1][2] %= MOD

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            # dp[i+1][3] %= MOD

    print(dp[N][3]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数
    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]

            dp[i+1][j]%=MOD
            
        ## カウント進める場合
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            # dp[i+1][1] %= MOD
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            # dp[i+1][2] %= MOD

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            # dp[i+1][3] %= MOD

    print(dp[N][3]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()