Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

q = int(1e9+7)

comb = [1]

for i in range(0, N):
    comb.append((comb[-1] * (N - i) * pow(i+1, q-2, q)) % q)

base = [pow(8, N-2, q)]
for i in range(2, N+1):
    base.append((base[-1] * pow(8, q-2, q)) % q)

ans = 0
for i in range(2, N + 1):
    ans = (ans + (base[i-2] * comb[i] * (pow(2, i, q) - 2)) % q) % q
print(ans)

Fixed submission:
N = int(input())

q = int(1e9+7)

print((pow(10, N, q) - 2 * pow(9, N, q) + pow(8, N, q)) % q)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
colors = input()
data = [int(c == 'R') for c in colors]

min_move = float('inf')

for i in range(N + 1):
    left = data[:i]
    lm = len(left) - sum(left)
    right = data[i:]
    rm = sum(right)
    move = min(lm, rm) + abs(lm - rm)
    min_move = min(min_move, move)

print(min_move)


Fixed submission:
N = int(input())
colors = input()
data = [int(c == 'R') for c in colors]

lm = 0
rm = sum(data)
min_move = rm

for i in range(N):
    if data[i]:
        rm -= 1
    else:
        lm += 1
    move = min(lm, rm) + abs(lm - rm)
    min_move = min(min_move, move)

print(min_move)
Buggy python submission (verdict: Runtime Error):
from collections import deque
from copy import copy

N = int(input())
result = [0]*N

if N < 6:
    for i in range(N):
        print(0)
    exit()

result[5] += 1

coord = deque()
coord.append([[1,1,1], 6, 0])

while len(coord):
    sol, ans, level = coord.popleft()
    for i in range(level, 3):
        new_sol = copy(sol)
        new_sol[i] += 1
        new_ans = ans + sum(sol) + sol[i] + 1
        if new_ans <= N:
            coord.append([new_sol, new_ans, i])
            result[new_ans] += 1

print(*result, sep='\n', end='')



Fixed submission:
from collections import deque
from copy import copy

N = int(input())
result = [0]*N

if N < 6:
    for i in range(N):
        print(0)
    exit()

result[5] += 1

coord = deque()
coord.append([[1, 1, 1], 6, 0])

while len(coord):
    sol, ans, level = coord.popleft()
    for i in range(level, 3):
        new_sol = copy(sol)
        new_sol[i] += 1
        new_ans = ans + sum(sol) + sol[i] + 1
        if new_ans <= N:
            coord.append([new_sol, new_ans, i])
            result[new_ans-1] += 1

print(*result, sep='\n', end='')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

total = 0
for i in range(1, N + 1):
    N_max = N // i * i
    num = N // i
    total += (N_max + i) * (num // 2)
    if num%2:
        total += (N_max + i) // 2
print(total)

Fixed submission:
N = int(input())

total = 0
for i in range(1, N + 1):
    a = N // i
    total += (a * i + i) * a
    # if num%2:
    #     total += (N_max + i) // 2
print(int(total / 2))
Buggy python submission (verdict: Runtime Error):
from itertools import takewhile
from functools import reduce

data_num = int(input())
data_list = [bin(int(num)) for num in input().split(' ')]

combine_data = reduce(lambda x, y: x or y, data_list)

results = takewhile(lambda x: x == '0', combine_data[::-1])

print(len(results))

Fixed submission:
from itertools import takewhile

data_num = int(input())
data_list = [bin(int(num)) for num in input().split(' ')]

results = [takewhile(lambda x: x == '0', data[::-1]) for data in data_list]

print(min([len(list(result)) for result in results]))
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=""
while n>0:
    n-=1
    ans+=chr(ord('a')+N%26)
    n//=26
    print(ans[::-1])

Fixed submission:
n=int(input())
ans=""
while n>0:
    n-=1
    ans+=chr(ord('a')+n%26)
    n//=26
print(ans[::-1])

Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=""
while N>0:
    n-=1
    ans+=chr(ord('a')+N%26)
    n//=26
    print(ans[::-1])

Fixed submission:
n=int(input())
ans=""
while n>0:
    n-=1
    ans+=chr(ord('a')+n%26)
    n//=26
print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
a,b=map(in,input().split())
print(a*b)

Fixed submission:
a,b=map(int,input().split())
print(a*b)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int, input().split()))
f=1
for i in range(n):
  f*=a[i]
if f>1000000000000000000:
  f=-1
print(f)

Fixed submission:
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    f=1
    if 0 in a:
        f=0
    for i in a:
        f*=i
        if f>1000000000000000000:
            print(-1)
            return 
    print(f)
solve()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))


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

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

B = sorted([(A[i], i + 1) for i in range(N)], reverse=True)
dp = defaultdict(int)

for S in range(1, N + 1):
    for x in range(S + 1):
        y = S - x
        candid = []
        if x >= 1:
            candid.append(dp[(x - 1, y)] + B[S - 1][0]
                          * (B[S - 1][1] - x))
        if y >= 1:
            candid.append(dp[(x, y - 1)] + B[S - 1][0]
                          * ((N - y + 1) - B[S - 1][1]))
        dp[(x, y)] = max(candid)

print(max([dp[(i, N - i)] for i in range(N + 1)]))


Fixed submission:
from collections import defaultdict

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

B = sorted([(A[i], i + 1) for i in range(N)], reverse=True)
dp = defaultdict(int)

for S in range(1, N + 1):
    for x in range(S + 1):
        y = S - x
        candid = []
        if x >= 1:
            candid.append(dp[(x - 1, y)] + B[S - 1][0]
                          * (B[S - 1][1] - x))
        if y >= 1:
            candid.append(dp[(x, y - 1)] + B[S - 1][0]
                          * ((N - y + 1) - B[S - 1][1]))
        dp[(x, y)] = max(candid)

print(max([dp[(i, N - i)] for i in range(N + 1)]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

L = ['R', 'G', 'B']
accum = [[0] * N for i in range(3)]
for i in range(3):
    l = L[i]
    if S[0] == l:
        accum[i][0] = 1
    for j in range(1, N):
        accum[i][j] = accum[i][j - 1] + (1 if S[j] == l else 0)

ans = 0
for j in range(1, N - 1):
    for i in range(j):
        if S[i] == S[j]:
            continue
        for k in range(3):
            if L[k] != S[i] and L[k] != S[j]:
                lk = L[k]
                ik = k
        ans += accum[ik][N - 1] - accum[ik][j]
        if 2 * (j + 1) - (i + 1) <= N and S[2 * (j + 1) - (i + 1) - 1] == lk:
            ans -= 1
print(ans)


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

L = ['R', 'G', 'B']
accum = [[0] * N for i in range(3)]
for i in range(3):
    l = L[i]
    if S[0] == l:
        accum[i][0] = 1
    for j in range(1, N):
        accum[i][j] = accum[i][j - 1] + (1 if S[j] == l else 0)

ans = 0
for j in range(1, N - 1):
    for i in range(j):
        if S[i] == S[j]:
            continue
        for k in range(3):
            if L[k] != S[i] and L[k] != S[j]:
                lk = L[k]
                ik = k
        ans += accum[ik][N - 1] - accum[ik][j]
        if 2 * (j + 1) - (i + 1) <= N and S[2 * (j + 1) - (i + 1) - 1] == lk:
            ans -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (sqrt(a) + sqrt(b) + 1e-11 < sqrt(c)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Fixed submission:
a, b, c = map(int, input().split())
print('Yes' if 4 * a * b < (c - a - b) * (c - a - b)
      and c - a - b > 0 else 'No')
Buggy python submission (verdict: Runtime Error):
print('Yes' if S != 'AAA' and S != 'BBB' else 'No')

Fixed submission:
S = input()
print('Yes' if S != 'AAA' and S != 'BBB' else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [(i + M[0][0] - 1) // M[0][0] * M[0][1] for i in range(H + 1)]
for i in range(N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print(dp[H])


Fixed submission:
H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [(j + M[0][0] - 1) // M[0][0] * M[0][1] for j in range(H + 1)]
for i in range(1, N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print(dp[H])
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = A[0]
for i in range(1, N):
    L = L * A[i] // gcd(L, A[i])

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


Fixed submission:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


Fixed submission:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), set(A))

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


Fixed submission:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
N, K, S = map(int, input().split())

M = 1_000_000_000
_S = M - 1 if S == M else M
print(' '.join(list(map(str, [S] * K + [_S] * (N - K)))))


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

M = 1000000000
_S = M - 1 if S == M else M
print(' '.join(list(map(str, [S] * K + [_S] * (N - K)))))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

inv_t = [0, 1] + [0] * (N - 2)
for i in range(2, N):
    inv_t[i] = inv_t[MOD % i] * (MOD - MOD // i) % MOD

A.sort()
ans = 0
C = 1
for i in range(K, N + 1):
    ans += (A[i - 1] - A[N - i]) * C
    ans %= MOD
    C = C * i * inv_t[i - K + 1]
    C %= MOD
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


def pow(x, t):
    if t == 0:
        return 1
    a = pow(x, t >> 1)
    return a * a * (x ** (t & 1)) % MOD


fact = [0] * N
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
ifact = [0] * N
ifact[N - 1] = pow(fact[N - 1], MOD - 2)
for i in range(N - 1, 0, -1):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * ifact[r] * ifact[n - r] % MOD


A.sort()
ans = 0
for i in range(K, N + 1):
    C = nCr(i - 1, K - 1)
    ans += A[i - 1] * C
    ans -= A[N - i] * C
    ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
from functools import reduce
N, M = map(int, input().split())
a = list(map(int, input().split()))

half_a = [ai // 2 for ai in a]
L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
print((M - L) // (2 * L) + 1)


Fixed submission:
from functools import reduce

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


def f(x):
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    return c


def gcd(x, y):
    return gcd(y, x % y) if y != 0 else x


nth = [f(ai) for ai in a]
if len(set(nth)) == 1:
    half_a = [ai >> 1 for ai in a]
    L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
    ans = (M - L) // (2 * L) + 1 if M >= L else 0
else:
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import gcd
from functools import reduce
N, M = map(int, input().split())
a = list(map(int, input().split()))

half_a = [ai // 2 for ai in a]
L = reduce(lambda x, y: x * y // gcd(x, y), half_a)


Fixed submission:
from functools import reduce

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


def f(x):
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    return c


def gcd(x, y):
    return gcd(y, x % y) if y != 0 else x


nth = [f(ai) for ai in a]
if len(set(nth)) == 1:
    half_a = [ai >> 1 for ai in a]
    L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
    ans = (M - L) // (2 * L) + 1 if M >= L else 0
else:
    ans = 0
print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
b = list(accumulate(A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += b[t] + A[i] * t
    m += t
print(ans)


Fixed submission:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, right - A[i])], M - m)
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
d = [0] * 100001
for i in range(N):
    d[A[i]] = 1
for i in range(100000, 0, -1):
    d[i - 1] += d[i]

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += sum(A[:t]) + A[i] * t
    m += t
print(ans)


Fixed submission:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, right - A[i])], M - m)
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]

dp = defaultdict(set)
dp[(0, 0)].add(abs(A[0][0] - B[0][0]))
for i in range(H):
    for j in range(W):
        d = abs(A[i][j] - B[i][j])
        if i > 0:
            for k in dp[(i - 1, j)]:
                dp[(i, j)].add(abs(k + d))
                dp[(i, j)].add(abs(k - d))
        if j > 0:
            for k in dp[(i, j - 1)]:
                dp[(i, j)].add(abs(k + d))
                dp[(i, j)].add(abs(k - d))
print(min(dp[(H - 1, W - 1)]))


Fixed submission:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]

dp = [[0] * W for i in range(H)]
dp[0][0] = 1 << (abs(A[0][0] - B[0][0]) + 6400)
for i in range(H):
    for j in range(W):
        d = abs(A[i][j] - B[i][j])
        if i > 0:
            dp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d
        if j > 0:
            dp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d
ans = 0
res = dp[H - 1][W - 1] >> 6400
while res & 1 == 0:
    res >>= 1
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

A.sort()
F.sort(reverse=True)

if sum(A) <= K:
    ans = 0
else:
    AF = [A[i] * F[i] for i in range(N)]
    high = max(AF)
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if AF[i] > mid:
                Ki -= A[i] - mid // F[i]
                if Ki < 0:
                    able = False
                    break
        if able:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)


Fixed submission:
import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F[::-1].sort()

sum_A = A.sum()
if sum_A <= K:
    ans = 0
else:
    high = (A * F).max()
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        if sum_A - np.minimum(A, mid // F).sum() <= K:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)

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

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

A.sort()
F.sort(reverse=True)

if sum(A) <= K:
    ans = 0
else:
    high = max([A[i] * F[i] for i in range(N)])
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if A[i] * F[i] > mid:
                Ki -= A[i] - mid // F[i]
                if Ki < 0:
                    able = False
                    break
        if able:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)


Fixed submission:
import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F[::-1].sort()

sum_A = A.sum()
if sum_A <= K:
    ans = 0
else:
    high = (A * F).max()
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        if sum_A - np.minimum(A, mid // F).sum() <= K:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

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

A, B = map(int, input().split())

N = math.gcd(A, B)
primes = []
if N % 2 == 0:
    primes.append(2)
for i in range(3, int(math.sqrt(N)) + 2, 2):
    if N % i == 0:
        for p in primes:
            if i % p == 0:
                break
        else:
            primes.append(i)
print(len(primes) + 1)


Fixed submission:
import math

A, B = map(int, input().split())

while B > 0:
    A, B = B, A % B
N = A

ans = 1
for i in [2] + list(range(3, int(math.sqrt(N)) + 2, 2)):
    if N % i == 0:
        while N % i == 0:
            N //= i
        ans += 1
if N > 1:
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()

MOD = 10 ** 9 + 7

dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    new_dp = [0] * 13
    if S[i] == '?':
        for j in range(10):
            for k in range(13):
                new_dp[(k * 10 + j) % 13] += dp[k]
                new_dp[(k * 10 + j) % 13] %= MOD
    else:
        j = int(S[i])
        for k in range(13):
            new_dp[(k * 10 + j) % 13] += dp[k]
            new_dp[(k * 10 + j) % 13] %= MOD
    dp = new_dp[:]
print(dp[5])


Fixed submission:
S = input()

MOD = 10 ** 9 + 7

dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    new_dp = [0] * 13
    if S[i] == '?':
        for j in range(10):
            for k in range(13):
                new_dp[(k * 10 + j) % 13] += dp[k]
                new_dp[(k * 10 + j) % 13] %= MOD
    else:
        j = int(S[i])
        for k in range(13):
            new_dp[(k * 10 + j) % 13] += dp[k]
            new_dp[(k * 10 + j) % 13] %= MOD
    dp = new_dp[:]
print(dp[5])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
A = [int(input()) for i in range(N)]

colors = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.insert(0, A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))


Fixed submission:
from collections import deque
import bisect

N = int(input())
A = [int(input()) for i in range(N)]

colors = deque()
for i in range(N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.appendleft(A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))

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

N = int(input())
A = [int(input()) for i in range(N)]

colors = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.insert(0, A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))


Fixed submission:
from collections import deque
import bisect

N = int(input())
A = [int(input()) for i in range(N)]

colors = deque()
for i in range(N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.appendleft(A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))