Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def next_locations(maze, H, W, i, j):
    if maze[i][j] == '#':
        return list()
    locations = list()
    if i - 1 >= 0 and maze[i - 1][j] == '.':
        locations.append((i - 1, j))
    if i + 1 < H and maze[i + 1][j] == '.':
        locations.append((i + 1, j))
    if j - 1 >= 0 and maze[i][j - 1] == '.':
        locations.append((i, j - 1))
    if j + 1 < W and maze[i][j + 1] == '.':
        locations.append((i, j + 1))
    return locations


def location_to_index(W, i, j):
    return W * i + j


def warshall_floyd(V, d):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min([d[i][j], d[i][k] + d[k][j]])
    return d


def main():
    H, W = list(map(int, input().split(' ')))
    INF = H * W
    maze = list()
    for _ in range(H):
        maze.append(input())
    d = [[INF for _ in range(H * W)] for _ in range(H * W)]
    for i in range(H):
        for j in range(W):
            from_index = location_to_index(W, i, j)
            locs = next_locations(maze, H, W, i, j)
            for loc in locs:
                to_index = location_to_index(W, loc[0], loc[1])
                d[from_index][to_index] = 1 if from_index != to_index else 0
    d = warshall_floyd(H * W, d)
    answer = 0
    for from_index in range(H * W):
        for to_index in range(H * W):
            dist = d[from_index][to_index]
            if dist == INF:
                continue
            if dist > answer:
                answer = dist
    print(answer)


if __name__ == '__main__':
    main()

Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def next_locations(maze, H, W, i, j):
    if maze[i][j] == '#':
        return list()
    locations = list()
    if i - 1 >= 0 and maze[i - 1][j] == '.':
        locations.append((i - 1, j))
    if i + 1 < H and maze[i + 1][j] == '.':
        locations.append((i + 1, j))
    if j - 1 >= 0 and maze[i][j - 1] == '.':
        locations.append((i, j - 1))
    if j + 1 < W and maze[i][j + 1] == '.':
        locations.append((i, j + 1))
    return locations


def location_to_index(W, i, j):
    return W * i + j


def main():
    H, W = list(map(int, input().split(' ')))
    INF = H * W
    maze = list()
    for _ in range(H):
        maze.append(input())
    d = [[INF for _ in range(H * W)] for _ in range(H * W)]
    for i in range(H):
        for j in range(W):
            from_index = location_to_index(W, i, j)
            locs = next_locations(maze, H, W, i, j)
            for loc in locs:
                to_index = location_to_index(W, loc[0], loc[1])
                d[from_index][to_index] = 1 if from_index != to_index else 0
    d = csgraph_from_dense(d, null_value=INF)
    d = floyd_warshall(d)
    answer = 0
    for from_index in range(H * W):
        for to_index in range(H * W):
            dist = d[from_index][to_index]
            if dist == float('inf'):
                continue
            if dist > answer:
                answer = dist
    print(int(answer))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from math import gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

Fixed submission:
from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    a, b = max([a, b]), min([a, b])
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcd_from_list(num_list):
    if len(num_list) == 1:
        return num_list[0]
    else:
        return gcd(num_list[0], gcd_from_list(num_list[1:]))


def lcm_from_list(num_list):
    gcd_of_input = gcd_from_list(num_list)
    num_list = list(set(num_list))
    lcm = num_list[0]
    for i in range(len(num_list) - 1):
        lcm = lcm * num_list[i + 1] // gcd_of_input
    return lcm


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm_A = lcm_from_list(half_A)
    num_multiples = M // lcm_A
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

Fixed submission:
from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# 【考察】
# 0-indexedで考える。Aは降順ソートして考える。
# まず、初期状態でTop Pに含まれる問題はすべて出題されうる。
# なので初期でTop q (q > P)の問題が出題されるか否かを考えていく。
# 最終的にTop Pに入れるか否かが問題なので、Top 1 ~ P-1の問題は無視。
# Top qの問題に毎回投票しつつ、Top P ~ q-1の問題になるべく投票しないようにしたい。
# そこで数列 A[P], A[P+1], ..., A[q-1] を考える。
# この中から最大でN-V個の数字を選んで1減らすことをM回繰り返し、
# すべてA[q]以下にすることができればTop qの問題は出題されうる。
# 当然A[P]-A[q] > Mだったら無理（出題されない）。
# 以後A[P]-A[q] <= Mとする。
# この時、(A[P]-A[q]) + (A[P+1]-A[q]) + ... + (A[q-1]-A[q]) <= M * (N-V) であればTop qのは出題可能。
# 整理すると A[P] + A[P+1] + ... + A[q-1] <= M * (N-V) + A[q] * (q-P) となるので、
# Aの累積和のデータを保持しておけば各qにおいてO(1)で出題可否が判定可能。


def main():
    # N, M, V, P = list(map(int, input().split()))
    # A = list(map(int, input().split()))
    with open('PastAGC/01-08.txt', 'r') as f:
        N, M, V, P = list(map(int, f.readline().split()))
        A = list(map(int, f.readline().split()))
    P -= 1  # to 0-indexed
    A.sort(reverse=True)  # 降順ソート
    cumsum = [0] * N
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = cumsum[i - 1] + A[i]
    q = P + 1
    while q < N:
        left = cumsum[q - 1]
        if P > 0:
            left -= cumsum[P - 1]
        right = M * (N - V) + A[q] * (q - P)
        if A[P] - A[q] > M or left > right:
            print(q)
            return
        q += 1
    print(q)


if __name__ == '__main__':
    main()

Fixed submission:
# 【考察】
# 0-indexedで考える。Aは降順ソートして考える。
# まず、初期状態でTop Pに含まれる問題はすべて出題されうる。
# なので初期でTop q (q > P)の問題が出題されるか否かを考えていく。
# 最終的にTop Pに入れるか否かが問題なので、Top 1 ~ P-1の問題は無視。
# Top qの問題に毎回投票しつつ、Top P ~ q-1の問題になるべく投票しないようにしたい。
# そこで数列 A[P], A[P+1], ..., A[q-1] を考える。
# この中から最大でN-V個の数字を選んで1減らすことをM回繰り返し、
# すべてA[q]以下にすることができればTop qの問題は出題されうる。
# 当然A[P]-A[q] > Mだったら無理（出題されない）。
# 以後A[P]-A[q] <= Mとする。
# この時、(A[P]-A[q]) + (A[P+1]-A[q]) + ... + (A[q-1]-A[q]) <= M * (N-V) であればTop qのは出題可能。
# 整理すると A[P] + A[P+1] + ... + A[q-1] <= M * (N-V) + A[q] * (q-P) となるので、
# Aの累積和のデータを保持しておけば各qにおいてO(1)で出題可否が判定可能。


def main():
    N, M, V, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    P -= 1  # to 0-indexed
    A.sort(reverse=True)  # 降順ソート
    cumsum = [0] * N
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = cumsum[i - 1] + A[i]
    q = P + 1
    while q < N:
        left = cumsum[q - 1]
        if P > 0:
            left -= cumsum[P - 1]
        right = M * (N - V) + A[q] * (q - P)
        if A[P] - A[q] > M or left > right:
            print(q)
            return
        q += 1
    print(q)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    # BFS
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  # from_node, to_node, color
    explored_nodes = [0]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored_nodes.append(n[1])
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if next_to_node in explored_nodes:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    # print answer
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


if __name__ == '__main__':
    main()

Fixed submission:
from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    # BFS
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  # from_node, to_node, color
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored[n[1]] = 1
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if explored[next_to_node] == 1:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    # print answer
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s) + 1
# max of...
#    * num of sequential '<' on the left side
#    * num of sequential '>' on the right side
def calc_left_num(st):
    num = 0
    length = len(st)
    for index in range(length - 1, -1, -1):
        if st[index] != '<':
            break
        num += 1
    return num
def calc_right_num(st):
    num = 0
    for c in st:
        if c != '>':
            break
        num += 1
    return num
li = list()
for i in range(n):
    left_num = calc_left_num(s[:i])
    right_num = calc_right_num(s[i:])
    if i == 0:
        li.append(right_num)
    elif i == n - 1:
        li.append(left_num)
    else:
        li.append(max([left_num, right_num]))
print(sum(li))

Fixed submission:
def main():
    S = input()
    smaller_cnt = [0]  # <
    seq_cnt = 0
    for c in S:
        if c != '<':
            seq_cnt = 0
        else:
            seq_cnt += 1
        smaller_cnt.append(seq_cnt)
    larger_cnt = [0]  # >
    for c in S[::-1]:
        if c != '>':
            seq_cnt = 0
        else:
            seq_cnt += 1
        larger_cnt.append(seq_cnt)
    larger_cnt.reverse()
    ans = 0
    for x, y in zip(smaller_cnt, larger_cnt):
        ans += max([x, y])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s) + 1
# max of...
#    * num of sequential '<' on the left side
#    * num of sequential '>' on the right side
li = list()
for i in range(n):
    left_str_rev = s[:i][::-1]
    left_num = left_str_rev.find('>')
    left_num = left_num if left_num >= 0 else len(left_str_rev)
    right_str = s[i:]
    right_num = right_str.find('<')
    right_num = right_num if right_num >= 0 else len(right_str)
    if i == 0:
        li.append(right_num)
    elif i == n - 1:
        li.append(left_num)
    else:
        li.append(max([left_num, right_num]))
print(sum(li))

Fixed submission:
def main():
    S = input()
    smaller_cnt = [0]  # <
    seq_cnt = 0
    for c in S:
        if c != '<':
            seq_cnt = 0
        else:
            seq_cnt += 1
        smaller_cnt.append(seq_cnt)
    larger_cnt = [0]  # >
    for c in S[::-1]:
        if c != '>':
            seq_cnt = 0
        else:
            seq_cnt += 1
        larger_cnt.append(seq_cnt)
    larger_cnt.reverse()
    ans = 0
    for x, y in zip(smaller_cnt, larger_cnt):
        ans += max([x, y])
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def is_triangle(a, b, c):
    return a < b + c and b < c + a and c < a + b


def main():
    N = int(input())
    L = list(map(int, input().split(' ')))
    L.sort()
    cnt = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if not is_triangle(L[j + 1], L[i], L[j]):
                # cannot construct with L[k] for all k > j
                continue
            if is_triangle(L[N - 1], L[i], L[j]):
                # can construct with L[k] for all k > j
                cnt += N - 1 - j
                continue
            # binary search
            ok = j + 1
            ng = N - 1
            while abs(ok - ng) > 1:
                mid = (ok + ng) // 2
                if is_triangle(L[mid], L[i], L[j]):
                    ok = mid
                else:
                    ng = mid
            cnt += ok - j
    print(cnt)


if __name__ == '__main__':
    main()

Fixed submission:
import bisect


def main():
    N = int(input())
    L = list(map(int, input().split(' ')))
    L.sort()
    cnt = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            index = bisect.bisect_left(L, L[i] + L[j])
            cnt += max([0, index - j - 1])
    print(cnt)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd  #  from python3.5, use math,gcd
from collections import defaultdict


def prime_factorization(x):
    res = defaultdict(int)
    n = 2
    while n <= x:
        while x % n == 0:
            res[n] += 1
            x //= n
        n += 1
    return res


def main():
    A, B = list(map(int, input().split(' ')))
    gcd_ab = gcd(A, B)
    pf = prime_factorization(gcd_ab)
    print(1 + len(pf.keys()))  # +1 for factor `1`


if __name__ == '__main__':
    main()

Fixed submission:
from fractions import gcd  #  from python3.5, use math,gcd
from collections import defaultdict


def prime_factorization(x):
    res = defaultdict(int)
    n = 2
    while n**2 <= x:
        while x % n == 0:
            res[n] += 1
            x //= n
        n += 1
    if x != 1:
        res[x] += 1
    return res


def main():
    A, B = list(map(int, input().split(' ')))
    gcd_ab = gcd(A, B)
    pf = prime_factorization(gcd_ab)
    print(1 + len(pf.keys()))  # +1 for factor `1`


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


def main():
    N = int(input())
    S = input()
    counter = defaultdict(int)
    for c in S:
        counter[c] += 1
    ans = 0
    for i in range(N - 1, 0, -1):
        ci = S[i]
        if counter[ci] <= 1:
            continue
        for j in range(i - ans - 1, -1, -1):
            cj = S[j]
            if cj != ci:
                continue
            k = 0
            while k + 1 <= min(j + 1, i - j - 1) and S[i - k - 1] == S[j - k - 1]:
                k += 1
            ans = max(ans, k + 1)
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    # flags[n][m]: n 番目の文字と同じ文字がその m 個後にあれば1
    flags = [[0] * N for _ in range(N)]
    for n, c in enumerate(S):
        for m in range(1, N - n):
            if c == S[n + m]:
                flags[n][m] = 1
    ans = 0
    for m in range(1, N):
        from_n = -1
        for to_n in range(N):
            if flags[to_n][m] == 0:
                ans = max(ans, min(m, to_n - from_n - 1))
                from_n = to_n
        if from_n != to_n:
            ans = max(ans, min(m, to_n - from_n - 1))
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import defaultdict


sys.setrecursionlimit(10**6)


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    # comb(p - 1, i)
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  # (- k)**(p - 1 - i)
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


if __name__ == '__main__':
    main()

Fixed submission:
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    # comb(p - 1, i)
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  # (- k)**(p - 1 - i)
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
                dp[i + 1][(10 * k + j) % 13] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()