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

from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    '''
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    '''
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)
    L_t = defaultdict(list)
    for i, l in enumerate(L):
        L_t[l].append(i)
    R_t = defaultdict(list)
    for j, r in enumerate(R):
        R_t[r].append(j)

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        if len(l_candidate) == 0 or len(r_candidate) == 0:
            continue
        else:
            cnt += len(l_candidate) * len(r_candidate)
            #answer_set = set()
            #print(x)
            #print(l_candidate)
            #print(r_candidate)
            #for i,j in itertools.product(l_candidate, r_candidate):
            #    answer_set.add((i,j))
            #cnt += len(answer_set)

    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#解説を見て実装
from collections import Counter

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめL_t = defaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    L_t = Counter(L)
    R_t = Counter(R)
    cnt = 0
    x_candidate = set(L) & set(R)
    for x in x_candidate:
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        cnt += l_candidate * r_candidate

    print(cnt)

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

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
ab = abs
n = k = ar = dp = 0

def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m,i = 1e9, x+1
	while i<n and i<x+k+1:
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
		i+=1
	dp[x] = m
	return dp[x]
 
def main():
	global n,ar,k,dp
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	pr(solve(0))
 
main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

def yakusu(n):
    max_yakusu = int(n**0.5)
    arr = [1]
    tmp = 2

    while n > 1:
        for i in range(tmp,max(n+1,max_yakusu+1)):
            if n % i == 0:
                arr.append(i)
                while n % i == 0:
                    n = int(n/i)
                    tmp = i + 1
                break
    return arr

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

A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)

koyaku_insu = yakusu(koyaku)


print(len(koyaku_insu))

### FIXED CODE ###

def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))
### BUGGY CODE ###

import sys

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

if (A+B) == K:
    print(0, 0)
    sys.exit()

for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1

print(A, B)

### FIXED CODE ###


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

if A >= K:
    print( A-K, B)
elif K <= A+B:
    print(0, B-(K-A))
else:
    print(0, 0)
### BUGGY CODE ###

s=input()
n=len(s)
a=b=0
M=10**9+7
for i in range(n):
  if'0'<s[i]:
    a+=2**b*3**(n-i-1)%M
    b+=1
print((a+2**b)%M)

### FIXED CODE ###

def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b=b*2%M
  print((a+b)%M)
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N, K = mis()
    A = lmis()
    A.sort(reverse=True)
    F = lmis()
    F.sort()
    #
    class solver:
        def __getitem__(self, score_limit):
            k = K
            for i in range(N):
                if A[i]*F[i] > score_limit:
                    k -= A[i] - score_limit//F[i]
                    if k < 0:
                        return False
            return True
        def __len__(self):
            return max(A)*max(F)
    #
    import bisect
    print(bisect.bisect_left(solver(), True))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N, K = mis()
    A = lmis()
    A.sort(reverse=True)
    F = lmis()
    F.sort()
    #
    class solver:
        def __getitem__(self, score_limit):
            k = K
            for i in range(N):
                if A[i]*F[i] > score_limit:
                    k -= A[i] - score_limit//F[i]
                    if k < 0:
                        return False
            return True
    #
    import bisect
    print(bisect.bisect_left(solver(), True, hi=A[0]*F[-1]))

main()
### BUGGY CODE ###

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    for i, j in Ad.copy().items():
        if 2*i == k:
            m = Ad[i]//2
            Ad[i] -= 2*m
            ans += m
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            Ad[i] -= m
            ans += m
        else:
            H[i] = j
print(ans)

### FIXED CODE ###

import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
A = list(set(A))
A.sort()
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    ml = bisect.bisect_left(A, k) 
    for i in A[:ml]:
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)
### BUGGY CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

H,W=map(int, input().split())
M = list( list(input()) for _ in range(H) )

p(H,W)
p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

p(M)


for h in range(H):
	for w in range(W-1):
		i=M[h][0+w]
		j=M[h][1+w]
		
		if i==0: continue
		if j==0: M[h][1+w]=i+1
		if j>i+1:M[h][1+w]=i+1

	for w in range(W-1):
		i=M[h][-1-w]
		j=M[h][-2-w]

		if i==0: continue
		if j==0: M[h][-2-w]=i+1
		if j>i+1:M[h][-2-w]=i+1

p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		j=M[1+h][w]
		
		if i==0: continue
		if j==0: M[1+h][w]=i+1
		if j>i+1:M[1+h][w]=i+1
	
	for h in range(H-1):
		i=M[-1-h][w]
		j=M[-2-h][w]
	
		if i==0: continue
		if j==0: M[-2-h][w]=i+1
		if j>i+1:M[-2-h][w]=i+1

p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )



### FIXED CODE ###

H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

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

# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)


### FIXED CODE ###

# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main_lte2(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

def main_lte3(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 累積輪
    table2 = [[0] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table2[i][j] = table2[i][j-1] + table[i][j]
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            ans += table2[i][q] - table2[i][p-1]
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 二次元累積輪
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i][j-1]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i-1][j]
    for p, q in PQq:
        ans = table[q][q] + table[p-1][p-1] - table[p-1][q] - table[q][p-1]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)
### BUGGY CODE ###

def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  a=set(a)
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

heap = []
for a in A:
	heappush(heap, (-a, 1))

while heap:
	a, n = heappop(heap)
	a = -a
	if K > 0:
		K -= 1
		a = a*n/(n+1)
		heappush(heap, (-a, n+1))
	else:
		heappush(heap, (-a, n))
		break
print(math.ceil(-heap[0][0]))


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

def is_ok(x):
	s = 0
	for a in A:
		s += math.ceil(a / x)-1
	return s <= K

l, r = 0, 10**9
while r-l > 1:
	m = (r+l)//2
	if is_ok(m):
		r = m
	else:
		l = m
print(r)
### BUGGY CODE ###

def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup:
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

        dup.add(a)

    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())


### FIXED CODE ###

def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup and is_ans[a] :
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

        dup.add(a)

    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())
### BUGGY CODE ###

#N, X, Y = map(int, input().split())
#l = [0 for _ in range(N-1)]
#for i in range(1, N+1):
#    for j in range(i+1,N+1):
#        n = min(j-i, abs(i-X)+1 + abs(j-Y))
#        l[n-1] +=1
#for m in l:
#    print(m)
inf = 100000
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] *N
for i in range(N):
    queue = []
    dist = [inf] *N
    def push(n, d):
        if dist[n] == inf:
            dist[n] = d
            queue.append(n)
    push(i, 0)
    while len(queue) > 0:
        q = queue.pop(0)
        if q-1 >=0:
            push(q-1, dist[q] + 1)
        if q+1 <N:
            push(q+1, dist[q] + 1)
        if q == X:
            push(Y, dist[q] + 1)
        if q == Y:
            push(X, dist[q] + 1)
    for d in dist:
        ans[d] += 1
for i in range(1, N):
    print(int(ans[i]/2))


### FIXED CODE ###

N, X, Y = map(int, input().split())
l = [0 for _ in range(N-1)]
for i in range(1, N+1):
    for j in range(i+1,N+1):
        n = min(j-i, abs(i-X)+1 + abs(j-Y))
        l[n-1] +=1
for m in l:
    print(m)
### BUGGY CODE ###

s1 = input()
s2 = input()
list = s1

count = 0
for i in range(len(list)):
    if s1[i] != s2[i]:
      s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
      count = count+1
    if s1[0:i] != s2[0:i]:
      break
    if count > 27:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")


### FIXED CODE ###

def translate(x,y):
    if x == y[0]:
      return y[1]
    if x == y[1]:
      return y[0]
    return x

s1 = list(input())
s2 = list(input())
list = s1

count = 0
for i in range(len(list)):
    if s1[i] != s2[i]:
      x = s1[i]
      y = s2[i]
      for j in range(len(s1)):
        if s1[j] == x:
          s1[j]=y
        elif s1[j] == y:
          s1[j]=x
      #s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
      #s1.replace( s1[i], "X").replace( s2[i], x).replace( 'X' , y)
      #s1 = list(map(translate, s1))
      
      count = count+1
    if count > 27:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")
### BUGGY CODE ###

s = list(map(ord, list(input())))
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk *= 2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        if dp[i+1][j+1][k] < dp[i][j][k] + 1:
          dp[i+1][j+1][k] = dp[i][j][k] + 1
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def search1(n) :
    ret = 0
    for g in range(n // A[0] + 1) :
        n -= g*A[0]
        for s in range(n // A[1] + 1) :
            n -= s*A[1]
            for b in range(n // A[2] + 1) :
                n -= b*A[2]
                ret = max(ret, n + g*B[0]+s*B[1]+b*B[2])
                n += b*A[2]
            n += s*A[1]
        n += g*A[0]

    return ret

def search2(n) :
    ret = 0
    for g in range(n // B[0] + 1) :
        n -= g*B[0]
        for s in range(n // B[1] + 1) :
            n -= s*B[1]
            for b in range(n // B[2] + 1) :
                n -= b*B[2]
                ret = max(ret, n + g*A[0]+s*A[1]+b*A[2])
                n += b*B[2]
            n += s*B[1]
        n += g*B[0]

    return ret

M = search1(N)
ret = search2(M)
print(ret)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def knapzap(N, A, B) :
    dp = [0] * (N + 1)

    for n in range(1, N + 1) :
        dp[n] = max(
            dp[n-1] + 1,
            dp[n-A[0]] + B[0] if n - A[0] >= 0 else 0,
            dp[n-A[1]] + B[1] if n - A[1] >= 0 else 0,
            dp[n-A[2]] + B[2] if n - A[2] >= 0 else 0
        )

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
for i in range(N):
  move = 0
  for j in range(i,N-1):   
    if H[j] < H[j+1]:
      break
    elif H[j] >= H[j+1]:
      move += 1
  if ans <= move:
    ans = move
print(ans)
  

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans=0
cnt=0
for i in range(1,n):
  if h[i]<=h[i-1]:
    cnt+=1
    if cnt>ans:
      ans=cnt
  else:
    cnt=0
print(ans)
### BUGGY CODE ###

import numpy as np

s = input()
buf = [0 for i in range(13)]
s = s[::-1]
n = len(s)
# print(s)

base = 10

if s[0] == "?":
    buf = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    buf[int(s[0])] = 1
# print(buf)
# print("############")
for i in range(1,n):
    base = base%13
    nbuf = [0 for j in range(13)]
    if s[i] == "?":
        ooo = [0 for j in range(13)]
        for j in range(10):
            temp = (base*j)%13
            ooo[temp] += 1
        # print(ooo)
        for j in range(13):
            for k in range(13):
                temp = (j+k)%13
                nbuf[temp]+= buf[k]*ooo[j]
                nbuf[temp] %= (10**9+7)
    else:
        for j in range(13):
            temp = j+int(s[i])*base
            temp %= 13
            nbuf[temp] += buf[j]
            nbuf[temp] %= (10 ** 9 + 7)
    base *= 10
    buf = nbuf
    # print(buf)
    # print("*********************")

# print(buf)
print(buf[5])


### FIXED CODE ###



s = input()
buf = [0 for i in range(13)]
s = s[::-1]
n = len(s)
# print(s)

base = 10

if s[0] == "?":
    buf = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    buf[int(s[0])] = 1
# print(buf)
# print("############")
for i in range(1,n):
    base = base%13
    nbuf = [0 for j in range(13)]
    if s[i] == "?":
        ooo = [0 for j in range(13)]
        for j in range(10):
            temp = (base*j)%13
            ooo[temp] += 1
        # print(ooo)
        for j in range(13):
            for k in range(13):
                temp = (j+k)%13
                nbuf[temp]+= buf[k]*ooo[j]
                nbuf[temp] %= (10**9+7)
    else:
        for j in range(13):
            temp = j+int(s[i])*base
            temp %= 13
            nbuf[temp] += buf[j]
            nbuf[temp] %= (10 ** 9 + 7)
    base *= 10
    buf = nbuf
    # print(buf)
    # print("*********************")

# print(buf)
print(buf[5])
### BUGGY CODE ###

def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    for i in range(K + 1):
        if i > 0:
            m = m * (N - i) // i
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())


### FIXED CODE ###

def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = inv[mod % i] * ((mod - mod // i) % mod)
    for i in range(K + 1):
        if i > 0:
            m = (m * (N - i) * inv[i]) % mod
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())
### BUGGY CODE ###

input1= input()
A = int(input1.split()[0])
B = int(input1.split()[1])


C = A * B

for i in range(C):
    while A%(i+2) == 0 and B%(i+2) == 0:
        C = C / (i+2)
        A = A / (i+2)
        B = B / (i+2)



print(int(C))

### FIXED CODE ###

import math

input1= input()
A = int(input1.split()[0])
B = int(input1.split()[1])


C = A * B
C_sqrt_int = int(math.sqrt(C))

for i in range(C_sqrt_int):
    while A%(i+2) == 0 and B%(i+2) == 0:
        C = C / (i+2)
        A = A / (i+2)
        B = B / (i+2)


print(int(C))
### BUGGY CODE ###

n=int(input())
vs=list(map(int,input().split()))
xs=vs[0::2]
ys=vs[1::2]
xfs=set(xs)
yfs=set(ys)
m=float('inf')
for xf in xfs:
    for yf in yfs:
        if not xf==yf:
            m=min(m,len(xs)-xs.count(xf)+len(ys)-ys.count(yf))
print(n//2 if m==float('inf') else m)


### FIXED CODE ###

from collections import Counter
n=int(input())
vs=list(map(int,input().split()))
xs=vs[0::2]
ys=vs[1::2]
cx=Counter(xs).most_common()
cy=Counter(ys).most_common()
if len(cx)==1:
    cx.append((0,0))
if len(cy)==1:
    cy.append((-1,0))
if not cx[0][0]==cy[0][0]:
    print(len(xs)-cx[0][1]+len(ys)-cy[0][1])
else:
    mx=len(xs)-cx[1][1]+len(ys)-cy[0][1]
    my=len(xs)-cx[0][1]+len(ys)-cy[1][1]
    print(min(mx,my))