Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
memo = {}

def dfs(i, ub):
    if i == K:
        return 1
    if (i, ub) in memo:
        return memo[(i, ub)]
    ret = 0
    x = 1
    while x <= ub and x * x <= N:
        ret = (ret + dfs(i+1, N // x)) % mod
        x += 1
    y = 1
    while y < N // y:
        cnt = min(N // y, ub) - min(N // (y + 1), ub)
        ret = (ret + cnt * dfs(i+1, y)) % mod
        y += 1
    memo[(i, ub)] = ret
    return ret

N, K = map(int, input().split())
mod = 10**9 + 7
print(dfs(0, N))

Fixed submission:
from itertools import accumulate

N, K = map(int, input().split())
mod = 10**9 + 7

xs = []
x = 1
while x * x <= N:
    xs.append(N // x)
    x += 1
s = x - 1
y = 1
while y < N // y:
    xs.append(y)
    y += 1
xs = list(set(xs))
xs.sort()
compress = {x : i for i, x in enumerate(xs)}

dp = [[0] * len(compress) for _ in range(K)]
for x, i in compress.items():
    dp[-1][i] = x

for k in range(K-1)[::-1]:
    cum = list(accumulate([0] + dp[k+1]))
    for x, i in compress.items():
        a = max(compress[N // x], compress[N // s])
        dp[k][i] = (cum[-1] - cum[a]) % mod

    b = 1
    cum = [0] * len(compress)
    while b < N // b:
        cnt = N // b - N // (b + 1)
        cum[compress[b]] = (cum[compress[b]] + cnt * dp[k+1][compress[b]]) % mod
        b += 1
    cum = list(accumulate([0] + cum))
    for x, i in compress.items():
        b = N // x
        if x <= b:
            continue
        dp[k][i] += cum[-1] - cum[compress[b]+1]
        dp[k][i] += (x - N // (b + 1)) * dp[k+1][compress[b]]
        dp[k][i] %= mod
print(dp[0][-1])

Buggy python submission (verdict: Time Limit Exceeded):
memo = {}

def dfs(i, ub):
    if (i, ub) in memo:
        return memo[(i, ub)]
    if i == K:
        return 1
    ret = 0
    x = 1
    while x <= ub:
        ret = (ret + dfs(i+1, N // x)) % mod
        x += 1
    memo[(i, ub)] = ret
    return ret

N, K = map(int, input().split())
mod = 10**9 + 7
print(dfs(0, N))

Fixed submission:
from itertools import accumulate

N, K = map(int, input().split())
mod = 10**9 + 7

xs = []
x = 1
while x * x <= N:
    xs.append(N // x)
    x += 1
s = x - 1
y = 1
while y < N // y:
    xs.append(y)
    y += 1
xs = list(set(xs))
xs.sort()
compress = {x : i for i, x in enumerate(xs)}

dp = [[0] * len(compress) for _ in range(K)]
for x, i in compress.items():
    dp[-1][i] = x

for k in range(K-1)[::-1]:
    cum = list(accumulate([0] + dp[k+1]))
    for x, i in compress.items():
        a = max(compress[N // x], compress[N // s])
        dp[k][i] = (cum[-1] - cum[a]) % mod

    b = 1
    cum = [0] * len(compress)
    while b < N // b:
        cnt = N // b - N // (b + 1)
        cum[compress[b]] = (cum[compress[b]] + cnt * dp[k+1][compress[b]]) % mod
        b += 1
    cum = list(accumulate([0] + cum))
    for x, i in compress.items():
        b = N // x
        if x <= b:
            continue
        dp[k][i] += cum[-1] - cum[compress[b]+1]
        dp[k][i] += (x - N // (b + 1)) * dp[k+1][compress[b]]
        dp[k][i] %= mod
print(dp[0][-1])
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
grid = [input() for i in range(H)]
L = [[0] * W for i in range(H)]
R = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            continue
        if i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
        if j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if grid[i][j] == '#':
            continue
        if i == H-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1
        if j == W-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
print(max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3for i in range(H) for j in range(W)))


Fixed submission:
import numpy as np

H, W = map(int, input().split())
grid = np.array([list(input()) for i in range(H)]) == '.'
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
for i in range(1, H):
    U[i] = (U[i-1] + 1) * grid[i-1]
for i in reversed(range(H-1)):
    D[i] = (D[i+1] + 1) * grid[i+1]
for i in range(1, W):
    L[:, i] = (L[:, i-1] + 1) * grid[:, i-1]
for i in reversed(range(W-1)):
    R[:, i] = (R[:, i+1] + 1) * grid[:, i+1]
print(((U + D + L + R) * grid).max() + 1)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
grid = [input() for i in range(H)]
count = [[[0, 0] for j in range(W)] for i in range(H)]
for i in range(H):
    row = '#' + grid[i] + '#'
    left = 0
    while True:
        right = row.find('#', left+1)
        if right == -1:
            break
        for j in range(left, right-1):
            count[i][j][0] = right - left - 1
        left = right
columns = list(zip(*grid))
for j in range(W):
    column = '#' + ''.join(columns[j]) + '#'
    left = 0
    while True:
        right = column.find('#', left+1)
        if right == -1:
            break
        for i in range(left, right-1):
            count[i][j][1] = right - left - 1
        left = right
print(max(sum(count[i][j]) for i in range(H) for j in range(W)) - 1)


Fixed submission:
import numpy as np

H, W = map(int, input().split())
grid = np.array([list(input()) for i in range(H)]) == '.'
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
for i in range(1, H):
    U[i] = (U[i-1] + 1) * grid[i-1]
for i in reversed(range(H-1)):
    D[i] = (D[i+1] + 1) * grid[i+1]
for i in range(1, W):
    L[:, i] = (L[:, i-1] + 1) * grid[:, i-1]
for i in reversed(range(W-1)):
    R[:, i] = (R[:, i+1] + 1) * grid[:, i+1]
print(((U + D + L + R) * grid).max() + 1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for _ in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, X))
    events.append((T-X, -X))
events.sort()
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')


Fixed submission:
from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = [None] * (2*N)
for i in range(N):
    S, T, X = map(int, input().split())
    events[2*i] = (S-X, X)
    events[2*i+1] = (T-X, -X)
events.sort(key=lambda x: x[0])
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if i < N and A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if i < N and A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]

for B, C in BC:
    A[0:B][A[0:B] < C] = C
    A.sort()
print(A.sum())


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if i < N and A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))


def dfs(u):
    for v, w in tree[u]:
        if color[v] == -1:
            color[v] = color[u] ^ (w % 2)
            dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))


Fixed submission:
import sys
sys.setrecursionlimit(100000)

N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))


def dfs(u):
    for v, w in tree[u]:
        if color[v] == -1:
            color[v] = color[u] ^ (w % 2)
            dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dist = [[float('inf')] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            queue = deque([(i, j)])
            while queue:
                a, b = queue.popleft()
                for da, db in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    na, nb = a + da, b + db
                    if 0 <= na < H and 0 <= nb < W and A[na][nb] == '.' and dist[na][nb] > dist[a][b] + 1:
                        dist[na][nb] = dist[a][b] + 1
                        queue.append((na, nb))
print(max(max(row) for row in dist))

Fixed submission:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dp = [[float('inf') if A[i][j] == '.' else 0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H):
    for j in range(W)[::-1]:
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H)[::-1]:
    for j in range(W):
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
print(max(max(row) for row in dp))
Buggy python submission (verdict: Runtime Error):
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a%b)
    }
}

fn main() {
    let N: usize = read_line().parse().unwrap();
    let A = read_vec();

    let mut left = vec![0; N];
    let mut right = vec![0; N];

    left[0] = A[0];
    for i in 1..N {
        left[i] = gcd(left[i-1], A[i]);
    }
    right[N-1] = A[N-1];
    for i in (0..N-1).rev() {
        right[i] = gcd(right[i+1], A[i]);
    }

    let mut max = right[1];
    for i in 1..N-1 {
        max = std::cmp::max(max, gcd(left[i-1], right[i+1]));
    }
    max = std::cmp::max(max, left[N-2]);
    println!("{}", max);
}


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


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

gcd_from_right = [0] * N
gcd_from_right[-1] = A[-1]
for i in reversed(range(N-1)):
    gcd_from_right[i] = gcd(A[i], gcd_from_right[i+1])

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)

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

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

gcd_from_right = [0] * N
gcd_from_right[-1] = A[-1]
for i in reversed(range(N-1)):
    gcd_from_right[i] = gcd(A[i], gcd_from_right[i+1])

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)


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


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

gcd_from_right = [0] * N
gcd_from_right[-1] = A[-1]
for i in reversed(range(N-1)):
    gcd_from_right[i] = gcd(A[i], gcd_from_right[i+1])

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = sorted((a + b for a in A for b in B), reverse=True)[:min(X*Y, K)]
C.sort()
ABC = sorted((ab + c for ab in AB for c in C), reverse=True)[:K]
print('\n'.join(map(str, ABC)))


Fixed submission:
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = sorted((a + b for a in A for b in B), reverse=True)[:min(X*Y, K)]
C.sort()

heap = []
min_sum = float('inf')
for ab in AB:
    if len(heap) < K:
        for c in C:
            heappush(heap, -(ab + c))
            min_sum = min(min_sum, ab + c)
    else:
        left = 0
        right = Z
        while left < right:
            mid = (left+right) // 2
            n = ab + C[mid]
            if n >= min_sum:
                left = mid + 1
            else:
                right = mid
            min_sum = min(min_sum, n)
        for c in C[:right]:
            heappush(heap, -(ab + c))


for i in range(K):
    print(-heappop(heap))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (N+1) # the largest number using i matches
for a in A:
    if count[a] <= N:
        dp[count[a]] = a
for i in range(N+1):
    if dp[i] == 0:
        continue
    for a in A:
        if i + count[a] <= N:
            dp[i+count[a]] = max(dp[i+count[a]], int(''.join(sorted(list(str(dp[i]) + str(a)), reverse=True))))
print(dp[N])



Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for _ in range(N+1)]
for i in range(N+1):
    if i > 0 and all(dp[i][j] == 0 for j in range(10)):
        continue
    for a in A:
        if i + count[a] <= N:
            ndp = list(dp[i])
            ndp[a] += 1
            ca = sum(ndp)
            cb = sum(dp[i+count[a]])
            if ca > cb:
                dp[i+count[a]] = ndp
            if ca == cb:
                for j in range(10)[::-1]:
                    if dp[i+count[a]][j] > ndp[j]:
                        break
                    if dp[i+count[a]][j] < ndp[j]:
                        dp[i+count[a]] = ndp
                        break
ans = ''
for i in range(10)[::-1]:
    ans += str(i) * dp[N][i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
is_root = [False] + [True] * N
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        parent[v] = u
        queue.append(v)
for i in range(1, N+1):
    print(parent[i])


Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
is_root = [False] + [True] * N
par_count = [0] * (N+1)
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    par_count[B] += 1
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        if par_count[v] > 1:
            par_count[v] -= 1
        else:
            parent[v] = u
            queue.append(v)
for i in range(1, N+1):
    print(parent[i])
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int64)
ans = np.identity(N, dtype=np.int64)
while K > 0:
    if K & 1 == 1:
        ans = np.matmul(ans, a) % mod
    a = np.matmul(a, a) % mod
    K >>= 1
print(np.sum(ans) % mod)

Fixed submission:
import sys
input = sys.stdin.readline

def matmul(a, b, mod):
    m = len(a)
    l = len(a[0])
    n = len(b[0])
    ret = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            e = 0
            for k in range(l):
                e = (e + a[i][k] * b[k][j]) % mod
            ret[i][j] = e
    return ret

mod = 10**9+7
N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
ans = [[i == j for j in range(N)] for i in range(N)]
while K > 0:
    if K & 1 == 1:
        ans = matmul(ans, a, mod)
    a = matmul(a, a, mod)
    K >>= 1
print(sum(sum(row) % mod for row in ans) % mod)
Buggy python submission (verdict: Runtime Error):
N = int(input())
for k in range(N+2):
    if k * (k-1) == 2 * N:
        S = [[] for _ in range(k+1)]
        n = 1
        for i in range(2, N+1):
            for j in range(1, i):
                S[i].append(n)
                S[j].append(n)
                n += 1
        print(k)
        for i in range(1, k+1):
            ans = [len(S[i])] + S[i]
            print(' '.join(map(str, ans)))
        exit()
print('No')

Fixed submission:
N = int(input())
for k in range(N+2):
    if k * (k-1) == 2 * N:
        S = [[] for _ in range(k+1)]
        n = 1
        for i in range(2, k+1):
            for j in range(1, i):
                S[i].append(n)
                S[j].append(n)
                n += 1
        print('Yes')
        print(k)
        for i in range(1, k+1):
            ans = [len(S[i])] + S[i]
            print(' '.join(map(str, ans)))
        exit()
print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += 3**cnt
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Fixed submission:
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += pow(3, cnt, mod)
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += 3**cnt
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + 3**cnt
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Fixed submission:
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += pow(3, cnt, mod)
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)