Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, k = map(int, input().split())
if a == b == c:
    print(0)
    exit()
for i in range(k):
    tmp1 = a+b
    tmp2 = b+c
    tmp3 = c+a
    a = tmp2
    b = tmp3
    c = tmp1
    if a-b > 10**18:
        print('Unfair')
        exit()
print(a-b)


Fixed submission:
a, b, c, k = map(int, input().split())
if a == b == c:
    print(0)
elif a-b > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print(a-b)
    else:
        print(b-a)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
a = set()
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        a.add(s[i:j])
print(sorted(list(a))[k - 1])


Fixed submission:
s = input()
k = int(input())
a = set()
for i in range(len(s) + 1):
    for j in range(1, 6):
        a.add(s[i:i + j])
print(sorted(list(a))[k])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
lis = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        lis.append(s[i:j])
print(sorted(list(set(lis)))[k - 1])

Fixed submission:
s = input()
k = int(input())
a = set()
for i in range(len(s) + 1):
    for j in range(1, 6):
        a.add(s[i:i + j])
print(sorted(list(a))[k])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    ans = 0
    cur = 0
    for j in range(n + 1):
        if i == j:
            continue
        if j == n:
            ans += abs(cur)
            break
        ans += abs(a[j] - cur)
        cur = a[j]
    print(ans)

Fixed submission:
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
# 累積和
cur = 0
b = []
for i in range(1, len(a)):
    b.append(abs(a[i] - cur))
    cur = a[i]
s = sum(b)

for i in range(1, n + 1):
    print(s + abs(a[i + 1] - a[i - 1]) - (abs(b[i - 1]) + abs(b[i])))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import sqrt

Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


# メモ化
dd = defaultdict(bool)

for l, r in lr:
    count = 0
    for i in range(l, r+1, 2):
        if dd[i]:
            count += 1
        else:
            dd[i] = is_prime(i) & is_prime((i+1)//2)
            if dd[i]:
                count += 1
    print(count)

Fixed submission:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
N = 10**5
c = [0] * (N+1)
tf = [False] * (N+1)

for i in range(2, N+1):
    if not tf[i]:
        for j in range(i*2, N+1, i):
            tf[j] = True
for i in range(3, N, 2):
    if not tf[i] and not tf[(i+1)//2]:
        c[i] += 1

for i in range(3, N, 1):
    c[i] += c[i-1]
for l, r in lr:
    print(c[r] - c[l-1])
Buggy python submission (verdict: Runtime Error):
r = int(input())
g = int(input())
print(2 * g - r

Fixed submission:
r = int(input())
g = int(input())
print(2 * g - r)
Buggy python submission (verdict: Runtime Error):
s = input()
count = 0
if len(set(s)) == 1:
    print(0)
    exit()
left = 0
right = len(s) - 1

ans = 0
while True:
    if (s[left] == 'x' and s[right] == 'x') or s[left] == s[right]:
        left += 1
        right -= 1
    elif s[left] == 'x' and s[right] != 'x':
        ans += 1
        left += 1
    elif s[left] != 'x' and s[right] == 'x':
        ans += 1
        right -= 1
    elif s[left] != 'x' and s[right] != 'x' and s[left] != s[right]:
        print(-1)
        exit()
    if left == right:
        break
print(ans)


Fixed submission:
s = input()
count = 0
if len(set(s)) == 1:
    print(0)
    exit()
left = 0
right = len(s) - 1

ans = 0
while True:
    if (s[left] == 'x' and s[right] == 'x') or s[left] == s[right]:
        left += 1
        right -= 1
    elif s[left] == 'x' and s[right] != 'x':
        ans += 1
        left += 1
    elif s[left] != 'x' and s[right] == 'x':
        ans += 1
        right -= 1
    elif s[left] != 'x' and s[right] != 'x' and s[left] != s[right]:
        print(-1)
        exit()
    if right <= left:
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
s = input()
rev_s = s[::-1]
count = 0
if len(set(s)) == 1:
    print(0)
    exit()
left = 0
right = len(s) - 1

ans = 0
while True:
    if (s[left] == 'x' and s[right] == 'x') or s[left] == s[right]:
        left += 1
        right -= 1
    if s[left] == 'x' and s[right] != 'x':
        ans += 1
        left += 1
    elif s[left] != 'x' and s[right] == 'x':
        ans += 1
        right -= 1
    elif s[left] != 'x' and s[right] != 'x' and s[left] != s[right]:
        print(-1)
        exit()
    if left == right:
        break
print(ans)

Fixed submission:
s = input()
count = 0
if len(set(s)) == 1:
    print(0)
    exit()
left = 0
right = len(s) - 1

ans = 0
while True:
    if (s[left] == 'x' and s[right] == 'x') or s[left] == s[right]:
        left += 1
        right -= 1
    elif s[left] == 'x' and s[right] != 'x':
        ans += 1
        left += 1
    elif s[left] != 'x' and s[right] == 'x':
        ans += 1
        right -= 1
    elif s[left] != 'x' and s[right] != 'x' and s[left] != s[right]:
        print(-1)
        exit()
    if right <= left:
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations


def warshall_floyd(d, n):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)


Fixed submission:
from itertools import permutations


def warshall_floyd(d, n):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

def warshall_floyd(d, n):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 道がない場合は除外
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
d = warshall_floyd(d, N)
ans = float('inf')
for perm in permutations(r):
    total = 0
    for i in range(1, len(perm)):
        total += d[perm[i-1]-1][perm[i]-1]
    ans = min(ans, total)
print(ans)


Fixed submission:
from itertools import permutations


def warshall_floyd(d, n):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
max_count = 0
for i in range(max(a) + 1):
    count = 0
    for j in range(n):
        if a[j] - 1 <= i <= a[j] + 1:
            count += 1
    max_count = max(max_count, count)
print(max_count)

Fixed submission:
import collections

n = int(input())
a = list(map(int, input().split()))
counter = collections.Counter(a)
max_count = 0
for i in range(0, max(a) + 1):
    max_count = max(max_count, counter[i - 1] + counter[i] + counter[i + 1])
print(max_count)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
uniq_a = sorted(list(set(a)), reverse=True)
c = 0
ans = 1
for num in uniq_a:
    if c == 0 and a.count(num) >= 4:
        print(num**2)
        exit()
    if a.count(num) >= 2:
        c += 1
        ans *= num
        if c == 2:
            print(ans)
            exit()
print(0)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)

flag = True
pairs = []
for i in range(1, len(a)):
    if flag:
        if a[i] == a[i-1]:
            pairs.append(a[i])
            if len(pairs) == 2:
                print(pairs[0]*pairs[1])
                exit()
            flag = False
    else:
        flag = True
print(0)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
uniq_a = sorted(list(set(a)), reverse=True)
c = 0
ans = 1
for num in uniq_a:
    if c == 0 and a.count(num) >= 4:
        print(num**2)
        exit()
    if a.count(num) >= 2:
        c += 1
        ans *= num
        if c == 2:
            print(ans)
            exit()
print(0)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)

flag = True
pairs = []
for i in range(1, len(a)):
    if flag:
        if a[i] == a[i-1]:
            pairs.append(a[i])
            if len(pairs) == 2:
                print(pairs[0]*pairs[1])
                exit()
            flag = False
    else:
        flag = True
print(0)
Buggy python submission (verdict: Runtime Error):
import math

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = x * a[i] // math.gcd(x, a[i])
    return x

n = int(input())
t = [int(input()) for _ in range(n)]
print(lcm(t))

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

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = x * a[i] // gcd(x, a[i])
    return x

n = int(input())
t = [int(input()) for _ in range(n)]
print(lcm(t))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(' '.join(map(str, b)))

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

b = []
if n % 2 == 0:
    for i in range(n//2):
        b.append(a[-1-i*2])
    for i in range(n//2):
        b.append(a[i*2])
else:
    for i in range(n//2+1):
        b.append(a[-1-i*2])
    for i in range(0, n//2):
        b.append(a[1+i*2])
print(' '.join(map(str, b)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = [int(input()) for _ in range(n)]


# total:累計, i:index
def dfs(total, i):
    if i == n:
        if total % 10 != 0:
            return total
        else:
            return 0
    return max(dfs(total, i + 1), dfs(total + s[i], i + 1))


print(dfs(0, 0))


Fixed submission:
n = int(input())
s = [int(input()) for _ in range(n)]

total = sum(s)
s.sort()
if total % 10 != 0:
    print(total)
else:
    for i in range(n):
        if (total - s[i]) % 10 != 0:
            print(total - s[i])
            exit()
    print(0)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

ans = 0
if a[0] > 0:
    op = "+"
elif a[0] < 0:
    op = "-"
elif a[0] == 0:
    ans += 1
    if a[1] > 0:
        a[0] = -1
    else:
        a[0] = 1

total = a[0]
for i in range(1, n):
    if (total+a[i]) >= 0 and op == "+":
        ans += abs((-1 - total) - a[i])
        total = -1
        op = "-"
    elif (total+a[i]) < 0 and op == "-":
        ans += abs((1 - total) - a[i])
        total = 1
        op = "+"
    elif total+a[i] == 0:
        ans += 1
        if a[1] > 0:
            a[0] = -1
        else:
            a[0] = 1
    else:
        total += a[i]
        if op == "+":
            op = "-"
        else:
            op = "+"
print(ans)

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


def check(op):  # 最初の数の正負を引数とする
    total = 0
    ans = 0
    for i in range(0, n):
        if (total+a[i]) > 0 and op == "+":
            ans += abs(-1 - (total + a[i]))
            total = -1
            op = "-"
        elif (total+a[i]) < 0 and op == "-":
            ans += abs(1 - (total + a[i]))
            total = 1
            op = "+"
        elif total+a[i] == 0:
            ans += 1
            if op == "+":
                total = -1
                op = "-"
            else:
                total = 1
                op = "+"
        else:
            total += a[i]
            if op == "+":
                op = "-"
            else:
                op = "+"
    return ans


print(min(check("+"), check("-")))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
for i in range(n):
    for j in range(n):
        flag = True
        for k in range(m):
            for l in range(m):
                if a[i+k][j+l] != b[k][l]:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            print('Yes')
            exit()
print('No')

Fixed submission:
n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
for i in range(n-m+1):
    for j in range(n-m+1):
        flag = True
        for k in range(m):
            for l in range(m):
                if a[i+k][j+l] != b[k][l]:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            print('Yes')
            exit()
print('No')
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
count = 0
for a in range(k + 1):
    for b in range(k + 1):
        for c in range(k + 1):
            if a + b + c == s:
                count += 1
print(count)

Fixed submission:
k, s = map(int, input().split())
count = 0
for a in range(k + 1):
    for b in range(k + 1):
        if 0 <= s - (a + b) <= k:
            count += 1
print(count)

Buggy python submission (verdict: Runtime Error):
k, s = map(int, input().split())
count = 0
for a in range(k):
    for b in range(k):
        for c in range(k):
            if a + b + c == S:
                count += 1
print(count)

Fixed submission:
k, s = map(int, input().split())
count = 0
for a in range(k + 1):
    for b in range(k + 1):
        if 0 <= s - (a + b) <= k:
            count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
a = input().split()
print(a[0][0] + a[1][0] + a[2][0])


Fixed submission:
s = input()
t = ''
add_list = ['dream', 'dreamer', 'erase', 'eraser']
cur = len(s)
for i in range(len(s)):
    if s[-1 - i:cur] in add_list:
        cur = -1 - i
if -cur == len(s):
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

x = 1
y = 1
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    for j in range(2, 10**18):
        if x <= a and y <= b:
            x = a
            y = b
            break
        else:
            a = ab[i][0] * j
            b = ab[i][1] * j
print(x + y)

Fixed submission:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

x = 1
y = 1
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    m = max(-(-x // a), -(-y // b))
    x = m * a
    y = m * b
print(x + y)
Buggy python submission (verdict: Time Limit Exceeded):
from operator import mul
from functools import reduce

a = int(input())
l = list(map(int, input().split()))
ans = reduce(mul, l) 
if 10**18 < ans:
  print(-1)
else:
  print(ans)

Fixed submission:
a = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 1
for i in range(a):
  ans = ans * l[i]
  if 10**18 < ans:
    ans = -1
    break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
a = int(input())
l = list(map(int, input().split()))
ans = 1
for i in range(a):
  ans = ans * l[i]
if 10**18 < ans:
  print(-1)
else:
  print(ans)

Fixed submission:
a = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 1
for i in range(a):
  ans = ans * l[i]
  if 10**18 < ans:
    ans = -1
    break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))

for i in range(n):
  print(l.count(i+1))

Fixed submission:
import collections

n = int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)

for i in range(n):
  print(c[i+1])
Buggy python submission (verdict: Runtime Error):
s = input()
p = "No"
a = 0
if len(s) % 2 == 0:
  for i in range(len(s)//2+1):
    if str(s[a]+s[a+1]) == "hi":
      p = "Yes"
      a = a + 2
    else:
      p = "No"
      break;
print(p)

Fixed submission:
s = input()
p = "No"
a = 0
if len(s) % 2 == 0:
  for i in range(len(s)//2):
    if str(s[a]+s[a+1]) == "hi":
      p = "Yes"
      a = a + 2
    else:
      p = "No"
      break;
print(p)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
c = 0
d = a+b
if a==0 and b==0:
    print(0)
elif a==0:
    print(0)
elif b==0:
    print(a)
else:   
    q, mod = divmod(n, d)      
    print(q*a + mod)

Fixed submission:
S = input()
if S[0] == S[1] and S[1] == S[2]:
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
p = "YES"

for i in range(n):
    if 1 < l.count(l[i]):
        p = "NO"
        break
    
print(p)

Fixed submission:
n = int(input())
l = list(map(int, input().split()))

if len(l) != len(set(l)):
    print("NO")
else:
    print("YES")

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
p = "YES"

for i in range(n):
    for j in range(n-i-1):
        if l[i] == l[i+1+j]:
            p = "NO"
    
print(p)

Fixed submission:
n = int(input())
l = list(map(int, input().split()))

if len(l) != len(set(l)):
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
a = int(input())
L = list(map(str, input().split()))
b = 'Three'
for i in range(a):
  if L[i] == 'Y':
    b = 'Four'
    break
print(b)

Fixed submission:
print(int(input()) // 3)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
p = 1

for i in range(N):
    p = p * (i+1)
p = p % (10 ** 9 +7)
print(p)

Fixed submission:
N = int(input())
p = 1
for i in range(N):
    p = p * (i+1)
    p = p % (10 ** 9 +7)
print(p)
Buggy python submission (verdict: Runtime Error):
N = int(input())
G = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append((b, i))
    G[b].append((a, i))

color = max(len(g) for g in G)
print(color)

ans = [-1] * (N-1)

def dfs(v=1, p=0, p_col=-1):
    col = 1

    for side, idx in G[v]:
        if side != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(side, v, col)
            col += 1

dfs()
print("\n".join(map(str, ans)))

Fixed submission:
import sys
sys.setrecursionlimit(500000)

N = int(input())
G = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append((b, i))
    G[b].append((a, i))

color = max(len(g) for g in G)
print(color)

ans = [-1] * (N-1)

def dfs(v=1, p=0, p_col=-1):
    col = 1

    for side, idx in G[v]:
        if side != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(side, v, col)
            col += 1

dfs()
print("\n".join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N == 1:
    print(0)
elif N == 2:
    print(1)
else:
    ans = int((N*(N-1))/2)
    print(ans)

Fixed submission:
S = list(input())
T = list(input())

ans = 0

for i in range(3):
    if S[i] == T[i]:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
S = input()
l = len(S)

dp = [[0 for i in range(13)] for j in range(l + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])

Fixed submission:
MOD = 10 ** 9 + 7
S = input()
l = len(S)

dp = [[0 for i in range(13)] for j in range(l + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])

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

s = sys.stdin.readline().strip()

MOD = 10 ** 9 + 7
mmap = []
for i in range(6):
    b = 10 ** i % 13
    mmap.append([[(b * i + j) % 13 for i in range(1,10)] for j in range(13)])

dp = [0] * 13
dp[0] = 1
j = 0
for c in reversed(s):
    tmp = dp.copy()

    if c == "0":
        pass
    elif c == "?":
        bset = mmap[j]
        for m, num in enumerate(tmp):
            if num == 0:
                continue
            for idx in bset[m]:
                dp[idx] += num
        
        for i in range(13):
            dp[i] %= MOD
    else:
        b = mmap[j][0][int(c) - 1]
        for n in range(13):
            idx = (n + b) % 13
            dp[idx] = tmp[n]
    
    if j==5:
        j = 0
    else:
        j+=1

print(dp[5])

Fixed submission:
MOD = 10 ** 9 + 7
S = input()
l = len(S)

dp = [[0 for i in range(13)] for j in range(l + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])