Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

import collections
from copy import copy


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def f(n):
    facs = factorization(n)
    res = set()

    def g(arr, total):
        if len(arr) == 0:
            res.add(total)
            return

        a, b = arr.pop()
        for i in range(0, b + 1):
            num = a ** i
            res.add(num)
            g(copy(arr), total * num)

    g(facs, 1)

    return res


def main():
    n = int(input())
    A = tuple(map(int, input().split()))
    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    ans = n
    for i in range(n):
        a = A[i]

        if D[a] > 1:
            ans -= 1
            continue

        if a == 1:
            continue

        res = f(a)
        res.remove(a)
        for num in res:
            if num in D:
                ans -= 1
                break

    print(ans)


main()


Fixed submission:

import collections

def main():
    n = int(input())
    A = sorted(map(int, input().split()))

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()

Buggy python submission (verdict: Time Limit Exceeded):

import collections

def main():
  n = int(input())
  A = tuple(sorted(map(int, input().split())))
  D = collections.defaultdict(int)
  for a in A:
    D[a] += 1

  ans = n
  for i in range(n):
    a = A[i]
    if D[a] > 1:
      ans -= 1
      continue

    for b in A[:i]:
      if a % b == 0:
        ans -= 1
        break

  print(ans)


main()


Fixed submission:

import collections

def main():
    n = int(input())
    A = sorted(map(int, input().split()))

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
  _n = int(input())
  ans = 1
  for num in map(int, input().split()):
    ans *= num

  print(ans if ans <= 10**18 else -1)

main()


Fixed submission:

def main():
  _n = int(input())
  ans = 1
  for num in map(int, input().split()):
    if num == 0:
      print(0)
      return

    if ans <= 10**18:
      ans *= num

  print(ans if ans <= 10**18 else -1)

main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
  s = tuple(map(int, input()[::-1]))

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for i in range(len(s)):
    t = t + s[i] * x
    counts[t % mod] += 1
    x = x * 10

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()


Fixed submission:

def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
  s = input()
  n = len(s)

  mod = 2019

  counts = {}
  counts[0] = 1

  prev = int(s[-1])
  counts[prev % mod] = 1
  for i in range(2, n + 1):
    t = (prev + int(s[-i]) * 10 ** (i - 1)) % mod
    if t in counts:
      counts[t] += 1
    else:
      counts[t] = 1

    prev = t

  ans = 0
  for count in counts.values():
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()


Fixed submission:

def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
  s = input()
  n = len(s)

  mod = 2019

  counts = [0] * mod
  counts[0] += 1

  prev = int(s[-1])
  counts[prev % mod] += 1
  for i in range(2, n + 1):
    t = prev + int(s[-i]) * 10 ** (i - 1)
    counts[t % mod] += 1
    prev = t

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()


Fixed submission:

def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def main():
  s = input()
  n = len(s)

  mod = 2019

  t_vals = [0] * n
  t_vals[-1] = int(s[-1])
  for i in range(2, n + 1):
    t_vals[-i] = t_vals[-i + 1] + int(s[-i]) * 10 ** (i - 1)

  counts = defaultdict(int)
  counts[0] = 1
  for t in t_vals:
    counts[t % mod] += 1

  ans = 0
  for count in counts.values():
    ans += count * (count - 1) // 2

  print(ans)

main()


Fixed submission:

def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)

  for nc_apple in r:
    apple = arr[0]
    if apple >= nc_apple: break

    arr.pop(0)
    arr.append(nc_apple)

  print(sum(arr))


main()


Fixed submission:

def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)
  new_num = 0

  for i, nc_apple in enumerate(r):
    if arr[i] >= nc_apple: break

    new_num += nc_apple - arr[i]

  print(sum(arr) + new_num)


main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)

  for nc_apple in r:
    apple = arr[0]
    if apple >= nc_apple: break

    arr[0] = nc_apple

    for i in range(len(arr) - 1):
      if arr[i] < arr[i + 1]: break

      arr[i], arr[i + 1] = arr[i + 1], arr[i]

  print(sum(arr))


main()


Fixed submission:

def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)
  new_num = 0

  for i, nc_apple in enumerate(r):
    if arr[i] >= nc_apple: break

    new_num += nc_apple - arr[i]

  print(sum(arr) + new_num)


main()
Buggy python submission (verdict: Runtime Error):

s = input()
q = int(input())

is_reverse = False
before = ""
after = ""

for _ in range(q):
  lst = input().split()
  if lst[0] == "1":
    is_reverse = not is_reverse
  else:
    _, f, c = lst
    if f == "1":
      if not is_reverse:
        before = c + before
      else:
        after = after + c
    else:
      if not is_reverse:
        after = after + c
      else:
        before = c + before

if is_reverse:
  before, after = after.reverse, before.reverse

print(before + s + after)


Fixed submission:

s = input()
q = int(input())

is_reverse = False
before = ""
after = ""

for _ in range(q):
  lst = input().split()
  if lst[0] == "1":
    is_reverse = not is_reverse
  else:
    _, f, c = lst
    if f == "1":
      if not is_reverse:
        before = c + before
      else:
        after = after + c
    else:
      if not is_reverse:
        after = after + c
      else:
        before = c + before

if is_reverse:
  s = s[::-1]
  before, after = after[::-1], before[::-1]

print(before + s + after)
Buggy python submission (verdict: Time Limit Exceeded):
S,T = input(), input()
operation = 0
for i in range(len(S)):
   if S[i]!=T[i]:
        S.replace(S[i],T[i])
        operation+=1    
print(operation)

Fixed submission:
S,T,operation = input(), input(),0
for i in range(len(S)):
   if S[i]!=T[i]: operation+=1    
print(operation)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
operation = 0
if len(S) == len(T):
    for i in range(len(S)):
        if S[i]!=T[i]:
            S.replace(S[i],T[i])
            operation+=1
    
print(operation)

Fixed submission:
S,T,operation = input(), input(),0
for i in range(len(S)):
   if S[i]!=T[i]: operation+=1    
print(operation)
Buggy python submission (verdict: Time Limit Exceeded):
n,ans=int(input()),0
for i in range(1, n+1):
    for j in range(i, n+1, i):ans+=j
print(ans)

Fixed submission:
from numba import jit
@jit
def Sum_divisors():
    n,ans=int(input()),0
    for i in range(1, n+1):
        for j in range(i, n+1, i):ans+=j
    print(ans)

Sum_divisors()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
for i in range(1, n+1):
    for j in range(i, n+1, i):
        ans+=j
print(ans)

Fixed submission:
from numba import jit
@jit
def Sum_divisors():
    n,ans=int(input()),0
    for i in range(1, n+1):
        for j in range(i, n+1, i):ans+=j
    print(ans)

Sum_divisors()
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
a,b = b,a
a,c = c,a
print(a," ",b,"

Fixed submission:
a,b,c = list(map(int,input().split()))
a,b = b,a
a,c = c,a
print(a,b,c)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
a,b = b,a
a,c = c,a
print(a," ",b,"

Fixed submission:
a,b,c = list(map(int,input().split()))
a,b = b,a
a,c = c,a
print(a,b,c)
Buggy python submission (verdict: Runtime Error):
a,b,c = list(map(int,input().split()))
a,b = b,a
a,c = c,a
print(a," ",b," ",c)

Fixed submission:
n,m = map(int,input().split())
a = list(map(int, input().split()))
popular = list(filter(lambda e: e>=(1/(4*m))*sum(a),a))
print("Yes" if len(popular) >= m else "No")
Buggy python submission (verdict: Time Limit Exceeded):
#


def main():
    a, b, n = map(int, input().split(" "))
    fac = 0
    for i in range(n + 1):
        j = i // b
        if j == 0:
            if fac < i:
                fac = i
        else:
            break
    ans = a * fac // b - a * (fac // b)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
#


def main():
    a, b, n = map(int, input().split(" "))
    fac = 0
    start = min(b, n)
    if b <= n:
        fac = start - 1
    else:
        fac = start
    ans = a * fac // b - a * (fac // b)
    print(ans)


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


def main():
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())
    for _ in range(q):
        command = sys.stdin.readline().strip().split(" ")
        if command[0] == "1":
            s = s[::-1]
        else:
            if command[1] == "1":
                s = command[2] + s
            else:
                s = s + command[2]
    print(s)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import deque


def main():
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())
    r = 0
    head = []
    bottom = []
    do_reverse = False
    for _ in range(q):
        command = sys.stdin.readline().strip().split(" ")
        # if command[0] == "1":
        #     s = s[::-1]
        # else:
        #     if command[1] == "1":
        #         s = command[2] + s
        #     else:
        #         s = s + command[2]
        if command[0] == "1":
            do_reverse = not do_reverse
            r += 1
        else:
            position_head = command[1] == "1"
            if do_reverse:
                position_head = not position_head
            if position_head:
                head.append(command[2])
            else:
                bottom.append(command[2])
    if r % 2 == 0:
        print("".join(head[::-1]) + s + "".join(bottom))
    else:
        print("".join(bottom[::-1]) + s[::-1] + "".join(head))


if __name__ == '__main__':
    main()

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


def main():
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())
    for _ in range(q):
        command = sys.stdin.readline().strip().split(" ")
        if command[0] == "1":
            s = s[::-1]
        else:
            if command[1] == "1":
                s = command[2] + s
            else:
                s = s + command[2]
    print(s)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import deque


def main():
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())
    r = 0
    head = []
    bottom = []
    do_reverse = False
    for _ in range(q):
        command = sys.stdin.readline().strip().split(" ")
        # if command[0] == "1":
        #     s = s[::-1]
        # else:
        #     if command[1] == "1":
        #         s = command[2] + s
        #     else:
        #         s = s + command[2]
        if command[0] == "1":
            do_reverse = not do_reverse
            r += 1
        else:
            position_head = command[1] == "1"
            if do_reverse:
                position_head = not position_head
            if position_head:
                head.append(command[2])
            else:
                bottom.append(command[2])
    if r % 2 == 0:
        print("".join(head[::-1]) + s + "".join(bottom))
    else:
        print("".join(bottom[::-1]) + s[::-1] + "".join(head))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        damage, cost = map(int, input().split(" "))
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            next_damage = min(total + damage, h)
            dp[next_damage] = min(dp[next_damage], dp[total] + cost)
    print(dp[-1])


if __name__ == '__main__':
    main()


Fixed submission:
# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        damage, cost = map(int, input().split(" "))
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            next_damage = min(total + damage, h)
            dp[next_damage] = min(dp[next_damage], dp[total] + cost)
    print(dp[-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    d = []
    c = []
    for _ in range(n):
        damage, cost = map(int, input().split(" "))
        d.append(damage)
        c.append(cost)
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            damage = min(total + d[i], h)
            dp[damage] = min(dp[damage], dp[total] + c[i])
    print(dp[-1])


if __name__ == '__main__':
    main()


Fixed submission:
# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        damage, cost = map(int, input().split(" "))
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            next_damage = min(total + damage, h)
            dp[next_damage] = min(dp[next_damage], dp[total] + cost)
    print(dp[-1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc148/tasks/abc148_c
import fractions
# math.gcdは3.5からなのでAtCoderで使えない
# import math


def main():
    (a, b) = [int(i) for i in input().split(" ")]
    print(int(a * b / fractions.gcd(a, b)))


if __name__ == '__main__':
    main()


Fixed submission:
# https://atcoder.jp/contests/abc148/tasks/abc148_a


def main():
    ans = [1,2,3]
    a = int(input())
    b = int(input())
    ans.remove(a)
    ans.remove(b)
    print(ans[0])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc148/tasks/abc148_c
import math


def main():
    (a, b) = [int(i) for i in input().split(" ")]
    print(int(a * b / math.gcd(a, b)))


if __name__ == '__main__':
    main()


Fixed submission:
# https://atcoder.jp/contests/abc148/tasks/abc148_c
import fractions
# math.gcdは3.5からなのでAtCoderで使えない
# import math


def main():
    (a, b) = [int(i) for i in input().split(" ")]
    print(int(a * b / fractions.gcd(a, b)))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc148/tasks/abc148_c
import math


def main():
    (a, b) = [int(i) for i in input().split(" ")]
    print(a * b // math.gcd(a, b))
    


if __name__ == '__main__':
    main()


Fixed submission:
# https://atcoder.jp/contests/abc148/tasks/abc148_c
import fractions
# math.gcdは3.5からなのでAtCoderで使えない
# import math


def main():
    (a, b) = [int(i) for i in input().split(" ")]
    print(int(a * b / fractions.gcd(a, b)))


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


def main():
    n = int(input())
    # if n % 2 == 0:
    #     print(n * (n // 2) + n // 2)
    # else:
    #     print(n * ceil(n / 2))
    t = 0
    for i in range(n):
        t += i
    print(t)


if __name__ == '__main__':
    main()


Fixed submission:
from math import ceil


def main():
    n = int(input()) - 1
    if n % 2 == 0:
        print(n * (n // 2) + n // 2)
    else:
        print(n * ceil(n / 2))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
dp_t = dict()
dp_p = dict()


def main():
    n = int(input())
    a = [int(s) for s in input().split(" ")]
    a.sort(reverse=True)
    max_comb = (0, 0)
    max_num = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            c = comb(a[i], a[j])
            if max_num < c:
                max_num = c
                max_comb = (a[i], a[j])
    print("%d %d" % max_comb)


def comb(n, r):
    t = 1
    if n in dp_t:
        t = dp_t[n]
    else:
        t = compute_kai(n)
    p = 1
    if (n, r) in dp_p:
        p = dp_p[(n, r)]
    else:
        pr = 1
        if r in dp_t:
            pr = dp_t[r]
        else:
            pr = compute_kai(r)
        if n - r in dp_t:
            p = dp_t[n - r]
        else:
            p = compute_kai(n -r)
        p *= pr
        dp_p[(n, r)] = p
    return t // p


def compute_kai(n):
    if n in dp_t:
        return dp_t[n]
    else:
        t = 1
        for i in range(n):
            t *= (n - i)
        dp_t[n] = t
        return t


if __name__ == '__main__':
    main()


Fixed submission:
dp_t = dict()
dp_p = dict()


def main():
    n = int(input())
    a = [int(s) for s in input().split(" ")]
    a.sort(reverse=True)
    t = a[0] // 2
    p = a[-1]
    if n == 2:
        print("%d %d" % (a[0], a[1]))
        return
    i = 1
    while a[i] > t:
        i += 1
        if i >= n:
            i -= 1
            break
    if abs(a[i - 1] - t) > abs(a[i] - t):
        p = a[i]
    else:
        p = a[i - 1]
    print("%d %d" % (a[0], p))


def main1():
    n = int(input())
    a = [int(s) for s in input().split(" ")]
    a.sort(reverse=True)
    max_comb = (0, 0)
    max_num = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            c = comb(a[i], a[j])
            if max_num < c:
                max_num = c
                max_comb = (a[i], a[j])
    print("%d %d" % max_comb)


def comb(n, r):
    t = 1
    if n in dp_t:
        t = dp_t[n]
    else:
        t = compute_kai(n)
    p = 1
    if (n, r) in dp_p:
        p = dp_p[(n, r)]
    else:
        pr = 1
        if r in dp_t:
            pr = dp_t[r]
        else:
            pr = compute_kai(r)
        if n - r in dp_t:
            p = dp_t[n - r]
        else:
            p = compute_kai(n -r)
        p *= pr
        dp_p[(n, r)] = p
    return t // p


def compute_kai(n):
    if n in dp_t:
        return dp_t[n]
    else:
        t = 1
        for i in range(n):
            t *= (n - i)
        dp_t[n] = t
        return t


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


s = input()


def main():
#    s = ['0' for _ in range(10**5)]
#   TLE check py3 だとちょっと遅いかもしれない？
    n = len(s)
    mod = 10**9 + 7

    dp = [[0]* 13 for _ in range(n+1)]
    dp[0][0] = 1

    #print(len(dp),len(dp[0]))

    # i : 桁数
    # j : 13で割った余り
    # k : ? をkと仮定
    # dp[i][j] : i+1 桁目 までの数字を13で割ったとき、余りがjになる数の個数
    for i in range(n):
        if s[i] != '?':

            c = int(s[i]) - int('0')
            for j in range(13):
                i_ = i+1
                j_ = (j*10+c); j_%=13
                dp[i_][j_] += dp[i][j]
                dp[i_][j_] %= mod
        else: 
            for j in range(13):
                for k in range(10):
                    i_ = i+1
                    j_ = j*10+k ; j_ %= 13
                    dp[i_][j_] += dp[i][j]
                    dp[i_][j_] %= mod

        # print(i,j,dp[i+1])
    print(dp[-1][5])      
     
main()
        


Fixed submission:


s = input()


def main():
#    s = ['0' for _ in range(10**5)]
#   TLE check py3 だとちょっと遅いかもしれない？
    n = len(s)
    mod = 10**9 + 7

    dp = [[0]* 13 for _ in range(n+1)]
    dp[0][0] = 1

    #print(len(dp),len(dp[0]))

    # i : 桁数
    # j : 13で割った余り
    # k : ? をkと仮定
    # dp[i][j] : i+1 桁目 までの数字を13で割ったとき、余りがjになる数の個数
    for i in range(n):
        if s[i] != '?':

            c = int(s[i]) - int('0')
            for j in range(13):
                i_ = i+1
                j_ = (j*10+c); j_%=13
                dp[i_][j_] += dp[i][j]
                dp[i_][j_] %= mod
        else: 
            for j in range(13):
                for k in range(10):
                    i_ = i+1
                    j_ = j*10+k ; j_ %= 13
                    dp[i_][j_] += dp[i][j]
                    dp[i_][j_] %= mod

        # print(i,j,dp[i+1])
    print(dp[-1][5])      
     
main()