Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import bisect

INF = 10 ** 10

N = int(input())
As = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(N-1)]

dfs_stack = [1]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for u, v in edges:
        if u == pos:
            if ans[v-1] == -1:
                dfs_stack.append(v)
            else:
                parent = v
        elif v == pos:
            if ans[u-1] == -1:
                dfs_stack.append(u)
            else:
                parent = u
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent-1]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos-1])
    rewinder.append( (index, lis[index], As[pos-1]) )
    lis[index] = As[pos-1]
    ans[pos-1] = lis.index(INF)

print(*ans, sep = '\n')

Fixed submission:
k = int(input())
a, b = map(int, input().split())

flg = False
for i in range(a, b+1):
    if i % k == 0:
        flg = True
        break

if flg:
    print("OK")
else:
    print("NG")
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7
N, K = map(int, input().split())

def gcd1_tuples(k):
    if gcd1_tuples.memo[k] != -1:
        return gcd1_tuples.memo[k]
    else:
        tmp = pow(k, N, mod)
        for j in range(2, k+1):
            tmp -= gcd1_tuples(k//j)
            tmp %= mod
        return tmp

gcd1_tuples.memo = [-1] * (K+1)
gcd1_tuples.memo[1] = 1

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)


Fixed submission:
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7
N, K = map(int, input().split())

gcd1_tuples = [0] * (K+1)

for i in range(1, K+1):
    gcd1_tuples[i] = pow(i, N, mod)
    for j in range(2, i+1):
        gcd1_tuples[i] -= gcd1_tuples[i//j]
    gcd1_tuples[i] %= mod

s = 0
for i in range(1, K+1):
    s += gcd1_tuples[K//i] * i
    s %= mod

print(s)


Fixed submission:
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
mod = 10 ** 9 + 7

s = 0
tmp = 1
for _ in range(N):
    tmp *= K
    tmp %= mod
s = tmp
for i in range(K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N):
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

Fixed submission:
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
mod = 10 ** 9 + 7

s = 0
tmp = 1
for _ in range(N)
    tmp *= K
    tmp %= mod
s = tmp
for i in range(K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N)
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

Fixed submission:
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

@lru_cache
def combination(n, k):
    if k == 0:
        return 1
    else:
        return ((combination(n, k-1) * (n-k+1) % MOD) * pow(k, MOD-2, MOD)) % MOD

n, k = map(int, input().split())

s = 0
for m in range(0, min(k+1, n)):
    s += combination(n, min(m, n - m)) * combination(n - 1, min(m, n - m - 1))
    s %= MOD

print(s)

Fixed submission:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

@lru_cache(None)
def combination(n, k):
    if k == 0:
        return 1
    else:
        return ((combination(n, k-1) * (n-k+1) % MOD) * pow(k, MOD-2, MOD)) % MOD

n, k = map(int, input().split())

s = 0
for m in range(0, min(k+1, n)):
    s += combination(n, min(m, n - m)) * combination(n - 1, min(m, n - m - 1))
    s %= MOD

print(s)
Buggy python submission (verdict: Runtime Error):
if A == B == C:
  print("No")
elif A == B or B == C or C == A:
  print("Yes")
else:
  print("No")

Fixed submission:
A, B, C = map(int, input().split())
if A == B == C:
  print("No")
elif A == B or B == C or C == A:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)


Fixed submission:
A, B, C = map(int, input().split())
if A == B == C:
  print("No")
elif A == B or B == C or C == A:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7
table_len = 10 ** 6 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(a, b):
    return fac[a+b] * finv[a] * finv[b] % MOD


r1, c1, r2, c2 = map(int, input().split())
ans = (comb(r1, c1) + comb(r2+1, c2+1) - comb(r1, c2+1) - comb(r2+1, c1)) % MOD
print(ans)


Fixed submission:
MOD = 10 ** 9 + 7
table_len = 2 * 10 ** 6 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(a, b):
    return fac[a+b] * finv[a] * finv[b] % MOD


r1, c1, r2, c2 = map(int, input().split())
ans = (comb(r1, c1) + comb(r2+1, c2+1) - comb(r1, c2+1) - comb(r2+1, c1)) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

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

print(min(dp[H:]))

Fixed submission:
from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

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

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0]

while dp[-1] < H:
    elem = 0
    for A, B in AB:
        if B <= len(dp): 
            elem = max(elem, dp[-B] + A)
    dp.append(elem)

print(len(dp) - 1)

Fixed submission:
from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

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

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0]

while dp[-1] < H:
    elem = 0
    for A, B in AB:
        if B <= len(dp): 
            elem = max(elem, dp[-B] + A)
    dp.append(elem)

print(len(dp) - 1)

Fixed submission:
from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

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

print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
ls = list(map(int, input().split())
counter = 1
for elem in ls:
    if elem == counter:
        counter += 1
print(N - counter)

Fixed submission:
N = int(input())
ls = list(map(int, input().split()))
counter = 1
for elem in ls:
    if elem == counter:
        counter += 1
if counter == 1:
    print(-1)
else:
    print(N - counter + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import defaultdict

N, K = map(int, input().split())
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    for i in range(len(ls)):
        for j in range(i+1, len(ls)):
            if ls[j] - ls[i] < K:
                ans += 1
            else:
                break
        
print(ans)

Fixed submission:
import numpy as np
from collections import defaultdict

N, K = map(int, input().split())
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    j = 1
    for i in range(len(ls)):
        while j < len(ls):
            if ls[j] - ls[i] < K:
                j += 1
            else:
                break
        ans += j - i - 1
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = np.full(N, INF, np.int64)
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

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

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = [INF] * N
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
Buggy python submission (verdict: Runtime Error):
t = sum(map(int, input())
if t % 2 == 0:
    print(t//2)
else:
    print("IMPOSSIBLE")

Fixed submission:
t = sum(map(int, input().split()))
if t % 2 == 0:
        print(t//2)
else:
        print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

print(dp[5])


Fixed submission:
MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

print(dp[5])
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

#nodes will be (steps % 3) * N + node

N, M = map(int, input().split())
start = []
goal = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    start.append(u)
    goal.append(N + v)

    start.append(N + u)
    goal.append(2*N + v)

    start.append(2*N + u)
    goal.append(v)

S, T = map(int, input().split())
    

cost = [1] * len(start)
digraph = csr_matrix((cost, (start, goal)), (3*N, 3*N))
ans = dijkstra(digraph, unweighted = True, indices = S-1)[T-1]
if ans == float("inf"):
    print(-1)
else:
    print(int(ans) // 3)

Fixed submission:
from collections import deque

#create digraph
#nodes will be (steps % 3) * N + node
N, M = map(int, input().split())
adj = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[      u].append(  N + v)
    adj[  N + u].append(2*N + v)
    adj[2*N + u].append(      v)

S, T = map(int, input().split())
S -= 1
T -= 1

#bfs
q = deque([S])
depth = [10 ** 9] * (3*N)
depth[S] = 0
while q:
    node = q.popleft()
    if node == T:
        break
    for next_node in adj[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.append(next_node)

if depth[T] == 10 ** 9:
    print(-1)
else:
    print(depth[T] // 3)

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
S, T = map(int, input().split())
    
#connect nodes which are 3 steps distant.
start = []
goal = []
for n0 in range(N):
    nodes_1_step  = set(adj[n0])
    nodes_2_steps = set()
    for n1 in nodes_1_step:
        nodes_2_steps |= set(adj[n1])
    nodes_3_steps = set()
    for n2 in nodes_2_steps:
        nodes_3_steps |= set(adj[n2])

    start += [n0] * len(nodes_3_steps)
    goal += list(nodes_3_steps)

cost = [1] * len(start)
digraph = csr_matrix((cost, (start, goal)), (N, N))

ans = dijkstra(digraph, unweighted = True, indices = S-1)[T-1]
    
if ans == float("inf"):
    print(-1)
else:
    print(int(ans))

Fixed submission:
from collections import deque

#create digraph
#nodes will be (steps % 3) * N + node
N, M = map(int, input().split())
adj = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[      u].append(  N + v)
    adj[  N + u].append(2*N + v)
    adj[2*N + u].append(      v)

S, T = map(int, input().split())
S -= 1
T -= 1

#bfs
q = deque([S])
depth = [10 ** 9] * (3*N)
depth[S] = 0
while q:
    node = q.popleft()
    if node == T:
        break
    for next_node in adj[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.append(next_node)

if depth[T] == 10 ** 9:
    print(-1)
else:
    print(depth[T] // 3)
Buggy python submission (verdict: Runtime Error):
from numba import njit

MOD = 10 ** 9 + 7

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

@njit
def solve(N, M, S, T):
    dp = [[1] * (M+1) for _ in range(N+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            if s != t:
                dp[i+1][j+1] -= dp[i][j]
            dp[i+1][j+1] %= MOD
    return dp[M][N]
    
print(solve(N, M, S, T))

Fixed submission:
MOD = 10 ** 9 + 7

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

dp = [[1] * (M+1) for _ in range(N+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        if s != t:
            dp[i+1][j+1] -= dp[i][j]
        dp[i+1][j+1] %= MOD

print(dp[N][M])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

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

dp = [[1] * (M+1) for _ in range(N+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        if s != t:
            dp[i+1][j+1] -= dp[i][j]
        dp[i+1][j+1] %= MOD

print(dp[N][M])


Fixed submission:
MOD = 10 ** 9 + 7

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

dp = [[1] * (M+1) for _ in range(N+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        if s != t:
            dp[i+1][j+1] -= dp[i][j]
        dp[i+1][j+1] %= MOD

print(dp[N][M])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import bisect
import numpy as np

MOD = 10 ** 9 + 7

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

S_appeared_indices = defaultdict(list)
for i, c1 in enumerate(S):
    S_appeared_indices[c1].append(i)

T_appeared_indices = defaultdict(list)
for j, c2 in enumerate(T):
    T_appeared_indices[c2].append(j)

dp = np.zeros((N+1, M+1), np.int64)
dp[0, :] = 1
dp[:, 0] = 1

for i, c1 in enumerate(S):
    for j, c2 in enumerate(T):
        dp[i+1, j+1] = dp[i+1, j]
        if c2 in S_appeared_indices:
            tmp = bisect.bisect_right(S_appeared_indices[c2], i) - 1
            while tmp >= 0:
                S_index = S_appeared_indices[c2][tmp]
                dp[i+1, j+1] += dp[S_index, j]
                tmp -= 1
        dp[i+1, j+1] %= MOD

print(dp[N, M])

    



Fixed submission:
MOD = 10 ** 9 + 7

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

dp = [[1] * (M+1) for _ in range(N+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        if s != t:
            dp[i+1][j+1] -= dp[i][j]
        dp[i+1][j+1] %= MOD

print(dp[N][M])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from math import log2
from collections import defaultdict
from operator import itemgetter
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7


BIT_len = 2 ** 18 # = 262144 > 200000
BIT_MOD = np.zeros(BIT_len+1, np.int64)

def BIT_add(index, elem):
    global BIT_len, BIT_MOD
    index += 1
    while index <= BIT_len:
        BIT_MOD[index] += elem
        BIT_MOD[index] %= MOD
        index += index & -index

def BIT_sum(index):
    global BIT_len, BIT_MOD
    index += 1
    s = 0
    while index != 0:
        s += BIT_MOD[index]
        s %= MOD
        index -= index & -index
    return s


d = defaultdict(list)

N = int(input())
for i in range(N):
    C = int(input())
    d[C].append(i)

pairs = []
for c, indices in d.items():
    for i in range(len(indices) - 1):
        if indices[i+1] - indices[i] > 1:
            pairs.append((indices[i], indices[i+1]))

pairs.sort(key = itemgetter(1))   


BIT_add(0, 1)
for start, end in pairs:
    BIT_add(end, BIT_sum(start))

print(BIT_sum(N))


Fixed submission:
import numpy as np
from collections import defaultdict
from operator import itemgetter
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7


d = defaultdict(list)

N = int(input())
for i in range(N):
    C = int(input())
    d[C].append(i)

pairs = []
for c, indices in d.items():
    for i in range(len(indices) - 1):
        if indices[i+1] - indices[i] > 1:
            pairs.append((indices[i], indices[i+1]))

pairs.sort(key = itemgetter(1))   


dp = np.zeros(N, np.int64)
dp[0] = 1
index = 0
for i in range(1, N):
    dp[i] = dp[i-1]
    while index < len(pairs) and pairs[index][1] == i:
        dp[i] += dp[pairs[index][0]] 
        index += 1
    dp[i] %= MOD

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    if i == 11:
        pass
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = str(max(int(A + dp[i - match[int(A)]]), int(dp[i - match[int(A)]] + A)))
            else:
                dp[i] = str(max(int(dp[i]), int(dp[i - match[int(A)]] + A)))
                dp[i] = str(max(int(dp[i]), int(A + dp[i - match[int(A)]])))

print(dp[N])

Fixed submission:
def max_for_str(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:#This case is unlikely to happen.
        for c1, c2 in zip(a, b):
            if c1 > c2:
                return a
            elif c1 < c2:
                return b
        return a
            
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = A + dp[i - match[int(A)]]
            else:
                dp[i] = max_for_str(dp[i] , A + dp[i - match[int(A)]])

print(dp[N])