Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set
import array

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: array[Cod] = []
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.append(item)
        # codList.setdefault(h, {})
        # codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row + 1, column + 1) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

A,B=map(int,input().split())
for x in range(2,A*B+1):
    if x%A==0 and x%B==0:
        print(x)
        exit()

### FIXED CODE ###

A,B=map(int,input().split())
for x in range(max(A,B),A*B+1,max(A,B)):
    if x%A==0:
        if x%B==0:
            print(x)
            exit()
### BUGGY CODE ###


def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)

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


    tmp = A[0]
    for a in A[1:]:
        tmp = lcm(tmp, a)

    B = [0] * N
    for i in range(N):
        B[i] = tmp // A[i]

    ans = 0
    for b in B:
        ans += b
        ans %= MOD
        

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd


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


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

def zalgo(S):
  N = len(S)
  res = [0] * N
  res[0] = N
  i = 1
  j = 0
  while i < N:
    while i + j < N and S[j] == S[i + j]:
      j += 1
    res[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N and k + res[k] < j:
      res[i + k] = res[k]
      k += 1
    i += k
    j -= k
  return res

res = 0
for i in range(N):
  T = S[i:]
  lcp = zalgo(T)
  for j in range(len(T)):
    l = min(lcp[j],j)
    if res < l:
      res = l

print(res)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

def zalgo(S):
  N = len(S)
  res = [0] * N
  res[0] = N
  i = 1
  j = 0
  while i < N:
    while i + j < N and S[j] == S[i + j]:
      j += 1
    res[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N and k + res[k] < j:
      res[i + k] = res[k]
      k += 1
    i += k
    j -= k
  return res

res = 0
for i in range(N):
  T = S[i:]
  lcp = zalgo(T)
  for j in range(len(T)):
    l = min(lcp[j],j)
    if res < l:
      res = l

print(res)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l][r] is None:
        memo[l][r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l][r]


n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

print(func(0, n - 1))


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

from collections import defaultdict
S = input()
S = S[::-1]

num = 0
ans = 0
memo = defaultdict(int)
memo[0] = 1
for i in range(len(S)):
    num += int(S[i])*pow(10,i)
    rest = num % 2019
    ans += memo[rest]
    memo[rest] += 1
print(ans)

### FIXED CODE ###

"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+(pow(10,i,2019)*int(S[i]))%2019)%2019
    ans += memo[num]
    memo[num] += 1

print(ans)
### BUGGY CODE ###

def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if i in P:
                prev = P.get(i - we, -1)
                if prev < P[i] + va:
                    P[i - we] = P[i] + va
                    max_ = max(P[i - we], max_)

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)


### FIXED CODE ###

def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[0] = target
    max_ = 0

    for vi in range(len(V)):
        we, va = W[vi], V[vi]
        for i in range(max_, -1, -1):
            if i in P:
                piva = P.get(i + va, -1)
                if piva < P[i] - we:
                    P[i + va] = P[i] - we
                    if max_ < i + va:
                        max_ = i + va
    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    temp = [0]*(len(A))
    prod = 1
    for i in range(len(A)):
        if i < K:
            prod *= A[i]
        else:
            prod = prod * A[i] // A[i - K]
        temp[i] = prod

    for i in range(N - K):
        if temp[i + K - 1] < temp[i + K]:
            print("Yes")
        else:
            print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    for i in range(N - K):
        if A[i] < A[i + K]:
            print("Yes")
        else:
            print("No")

if __name__ == '__main__':
    main()
### BUGGY CODE ###

K,S=map(int,input().split())
cnt=0
for x in range(K+1):
  for y in range(K+1):
    z=S-x-y
    if S==x+y+z and 0<=z and z<=K:
      cnt+=1
print(cnt)

### FIXED CODE ###

K,S=map(int,input().split())
cnt=0
for x in range(K+1):
  for y in range(K+1):
    z=S-x-y
    if 0<=z and z<=K:
      cnt+=1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
countalist = []
for i in a:
  countalist.append(a.count(i))
if max(countalist) >= 2:
  print('NO')
else:
  print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sorta = sorted(a)
sflag = False
for i in range(n - 1):
  if sorta[i] == sorta[i + 1]:
    sflag = True
    break
if sflag == True:
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [1 for i in range(N)]
for i in range(N):
    if B[i] != 0:
        for j in range(i+1, N):
            if A[i] == A[j]:
                B[i] = 0
                B[j] = 0
            elif A[j] % A[i] == 0:
                B[j] = 0
print(sum(B))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
LN = max(A) + 1
L = [0 for i in range(LN)]
count = 0
for i in A:
    for j in range(i, LN, i):
        L[j] += 1
for i in A:
    if L[i] == 1:
        count += 1
print(count)
### BUGGY CODE ###

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

def abs(a):
    if a>=0:
        return a
    else:
        return -a

while True:
    b=n
    n=abs(n-k)
    if b<=n:
        print(b)
        break


### FIXED CODE ###

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

def abs(a):
    if a>=0:
        return a
    else:
        return -a

m=n%k

while True:
    b=m
    m=abs(m-k)
    if b<=m:
        print(b)
        break
### BUGGY CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0

for i in range(n//r+1):
	tmp -= i*r
	tmp1 = tmp
	for j in range(n//g+1):
		tmp1 -= j*g
		if tmp1 >= 0 and tmp1%b==0:
			res+=1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)

### FIXED CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0
re=n//r+1
ge=n//g+1

for i in range(re):
	tmp = tmp - i*r
	tmp1 = tmp
	for j in range(ge):
		tmp1 = tmp - j*g
		if tmp1 >= 0 and tmp1%b==0:
			res = res + 1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)
### BUGGY CODE ###

import fractions
N = int(input())
A_array = list(map(int, input().split()))

gcd_max = 1

if N == 2:
    print(max(A_array[0],A_array[1]))
    exit()
for i in range(N):
    gcd = 0
    for j, A in enumerate(A_array):
        if i == j:
            continue
        if gcd == 0:
            gcd = A
            continue
        # print(A,gcd)
        gcd = min(gcd, fractions.gcd(A, gcd))
    gcd_max = max(gcd_max, gcd)
print(gcd_max)

### FIXED CODE ###

import fractions
N = int(input())
A_array = list(map(int, input().split()))

if N == 2:
    print(max(A_array[0], A_array[1]))
    exit()

remove_index = []
for i, A in enumerate(A_array):
    if i == 0:
        gcd_max = A
        remove_index.append(i)
        continue
    gcd = fractions.gcd(gcd_max, A)
    # print(i, gcd_max, gcd)
    if gcd_max > gcd:
        gcd_max = gcd
        remove_index.append(i)
# print(remove_index)
# print(gcd_max, remove_index)

gcd_ans = gcd_max
for index in remove_index:
    gcd = 0
    for i, A in enumerate(A_array):
        if i == index:
            continue
        if gcd == 0:
            gcd = A
            continue
        # print(gcd,A)
        gcd = fractions.gcd(gcd, A)
        if gcd_ans >= gcd:
            break
    # print(gcd_ans,gcd)
    gcd_ans = max(gcd_ans, gcd)
print(gcd_ans)
### BUGGY CODE ###

from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10**6, space=4)
    D[y, x] = 0
    
    walk = list(zip([1, 0, -1, 0], [0, 1, 0, -1]))
    warp = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2)
            if abs(dx)+abs(dy) >= 2]
    while Q:
        x, y = Q.pop()
        if G[y, x] == '!':
            continue
        d = D[y, x]
        G[y, x] = '!'
        
        for dx, dy in walk:
            nx, ny = x+dx, y+dy
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d:
                D[ny, nx] = d
                Q.append((nx, ny))
        for dx, dy in warp:
            nx, ny = x+dx, y+dy                
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d+1:
                D[ny, nx] = d+1
                Q.appendleft((nx, ny))
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

a,b,x=map(int,input().split())
print(sum(y%x==0 for y in range(a,b+1)))

### FIXED CODE ###

a,b,x=map(int,input().split());print(b//x-~-a//x)
### BUGGY CODE ###

K = int(input())

r = 1
N = 0
while True:
    N += 7*(10**(r-1))
    if N%K ==0:
        break
    r += 1

print(r)


### FIXED CODE ###

K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : ARC D問題
Author     : Kitaura Hiromi
LastUpdate : 20180526
Since      : 20180526
"""
from operator import xor
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    for j in range(i+1, N+1):

        # print("sum", sum(A[i:j]), "xor",  int(tmp))
        if sum(A[i:j]) == int(reduce(xor, A[i:j])):
            cnt += 1
        else:
            break
print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : ARC D問題
Author     : Kitaura Hiromi
LastUpdate : 20180527
Since      : 20180526
"""
from operator import xor
from functools import reduce

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

cnt = 0
r = 0
tmp = 0
for l in range(N):
    while r < N and tmp & A[r] == 0:
        # 区間の右端の要素を足す
        tmp ^= A[r]
        r += 1
    # print(l, r)
    cnt += (r - l)
    # 区間の左端の要素を引く
    tmp ^= A[l]
print(cnt)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1    

    for k in c.keys():
        a = c[k]
        ans += (a * (a-1)) // 2
print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
        p %= P
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
  for j in range(n):
    if A[i] % A[j] == 0 and i != j:
      ans += 1
      break
print(n - ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
    if a[i] not in b:
        for j in range(1, 10**6//a[i]+1):
            b[a[i]*j] = 1
        if a[i] != a[i+1]:
            c += 1
print(c)
### BUGGY CODE ###

def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    p = [i for i in range(2,a[-1]+1)]
    for i in range(len(p)-1):
        if p[i]==0:
            continue
        for j in range(i+1,len(p)):
            if p[j]%p[i] == 0:
                p[j]=0
    prm = []
    for p_ in p:
        if p_ != 0:
            prm.append(p_)
    for p in prm:
        cnt = 0
        for a_ in a:
            if a_%p==0:
                cnt += 1
        if cnt == n:
            print('not coprime')
            return
        if cnt > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]+1):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = {}
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            if prm.get(p_)==None:
                prm[p_] = 1
            else:
                print('setwise coprime')
                return
    print('pairwise coprime')

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
counter=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if((i*j+k)==n):
                counter=counter+1
print(counter)

### FIXED CODE ###

n=int(input())
counter=0
for i in range(1,n+1):
    counter=counter+(n-1)//i
print(counter)
### BUGGY CODE ###


N,K = list(map(int,input().split()))
balls = []
bucket = [0]*(N+1)

balls = list(map(int,input().split()))
balls.sort()

for ball_number in balls:
    bucket[ball_number] += 1

def judge(number_of_types, types):
    if number_of_types <= types:
        return True

number_of_types = 0
for i in bucket:
    if i >= 1:
        number_of_types += 1

if number_of_types <= K:
    print("0")
    quit()
else:
    count = 0
    for i in range(1,N+1):
        for j in bucket:
            if j == i:
                count += i
                number_of_types -= 1
                if judge(number_of_types, K):
                    print(count)
                    quit()

### FIXED CODE ###

N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()
bucket=[0*i for i in range(N+1)]
count=1
types=1
for i in range(1,N):
    if A[i]==A[i-1]:
        if i!=N-1:
            count+=1
        else:
            count+=1
            bucket[count]+=1
            break
    else:
        types+=1
        if i!=N-1:
            bucket[count]+=1
            count=1
        else:
            bucket[count]+=1
            bucket[1]+=1
            break

i=1
number_of_changes=0
while True:
    if types<=K:
        print(0)
        quit()
    elif types-bucket[i]<=K:
        print((types-K)*i+number_of_changes)
        quit()
    else:
        types-=bucket[i]
        number_of_changes+=bucket[i]*i
    i+=1
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

answer = [max(A[0],A[1])]

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i], sum(A[:i-1:2])))

print(answer[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

answer = [max(A[0],A[1])]

list_sum = A[::2]
for i in range(1,len(list_sum)):
  list_sum[i] += list_sum[i-1]

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i], list_sum[(i-1)//2]))

print(answer[-1])
### BUGGY CODE ###

N=int(input())
p=list(map(float,input().split()))
dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(N):
        dp[i+1][j]+=dp[i][j]*(1-p[i])
        dp[i+1][j+1]+=dp[i][j]*p[i]
print(sum(dp[-1][N//2+1:]))

### FIXED CODE ###

N=int(input())
p=list(map(float,input().split()))
dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(N):
        dp[i+1][j]+=dp[i][j]*(1-p[i])
        dp[i+1][j+1]+=dp[i][j]*p[i]
print(sum(dp[-1][N//2+1:]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
for i in range(M):
    A[-1] = A[-1]//2
    A.sort()
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for i in range(M):
    max_ = heapq.heappop(A)
    max_ = -max_//2
    heapq.heappush(A, -max_)
print(-sum(A))
### BUGGY CODE ###

S = input()
text = S[::-1]
DP = [[0] * 13 for _ in range(len(S))]

if text[0] == '?':
    for i in range(10):
        DP[0][i] = 1
else:
    DP[0][int(text[0])] = 1

for i in range(1, len(S)):
    if text[i] == '?':
        for x in range(10):
            nx = x * 10 ** i
            for k in range(13):
                t = (nx + k) % 13
                DP[i][t] += DP[i-1][k]
    else:
        y = int(text[i]) * 10 ** i
        for k in range(13):
            t = (y+k) % 13
            DP[i][t] = DP[i-1][k]

ans = DP[len(S)-1][5] % (10**9 + 7)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()