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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m = map(int, input().split())
data = []
row = []
col = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    data.append(1)
    row.append(a)
    col.append(b)
graph = csr_matrix((data, (row, col)), shape=(n, n))
_, p = dijkstra(graph, return_predecessors=True, unweighted=True, directed=False, indices=0, limit=n)
for item in p[1:]:
    if(item < 0):
        print("No")
        exit()
print("Yes")
for item in p[1:]:
    print(item + 1)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def bfs(v):
    q = deque()
    visited[v] = True
    q.append(v)
    while q:
        v = q.popleft()
        for child in edges[v]:
            if not visited[child]:
                visited[child] = True
                prev[child] = v
                q.append(child)

bfs(0)
print("Yes")
for i in range(1, n):
    print(prev[i] + 1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
for i in range(1,n):
    count=0
    for j in range(i-1,n-1):
        if l[j]==i:
            count+=1
    print(count)
print(0)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
m=[0]*n
for i in l:
    m[i-1]+=1
for j in range(n):
    print(m[j])
### BUGGY CODE ###

import itertools

while 1:
    try:
        a, b= map(int, raw_input().split())
        GCD = a * b
        LCM = 0
        # GCD
        for i, j in itertools.product(range((a if a > b else b) / 2), repeat=2):
          if a * (i+1) == b * (j+1) and GCD > a * (i+1):
            GCD = a * (i+1)
        # LCM 
        for i in range(a if a > b else b, 1, -1):
            if a % i == 0 and b % i == 0:
                LCM = i
                break
        print str(GCD) + " " + str(LCM)
    except:
        break

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
#sum_a = []
#sum_b = []
ans_a = 0
ans_b = 0
for i in range(n):
    if i%2==0:
        if sum(a[:i+1])>0:
            #sum_a.append(sum(a[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(a[:i+1]))+1
            a[i] += tmp
            ans_a += tmp
            #sum_a.append(sum(a[:i+1]))
    else:
        if sum(a[:i+1])<0:
            #sum_a.append(sum(a[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(a[:i+1]))+1
            a[i] -= tmp
            ans_a += tmp
            #sum_a.append(sum(a[:i+1]))
    if i%2==1:
        if sum(b[:i+1])>0:
            #sum_b.append(sum(b[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(b[:i+1]))+1
            b[i] += tmp
            ans_b += tmp
            #sum_b.append(sum(b[:i+1]))
    else:
        if sum(b[:i+1])<0:
            #sum_b.append(sum(b[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(b[:i+1]))+1
            b[i] -= tmp
            ans_b += tmp
            #sum_b.append(sum(b[:i+1]))

#print(a)
#print(sum_a)
print(min(ans_a,ans_b))

### FIXED CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
ans_a = 0
ans_b = 0
sum_a = 0
sum_b = 0
for i in range(n):
    if i%2==0:
        if sum_a+a[i]>0:
            tmp = 0
        else:
            tmp = abs(sum_a+a[i])+1
            a[i] += tmp
            ans_a += tmp
    else:
        if sum_a+a[i]<0:
            tmp = 0
        else:
            tmp = abs(sum_a+a[i])+1
            a[i] -= tmp
            ans_a += tmp
    sum_a+=a[i]
    if i%2==1:
        if sum_b+b[i]>0:
            tmp = 0
        else:
            tmp = abs(sum_b+b[i])+1
            b[i] += tmp
            ans_b += tmp
    else:
        if sum_b+b[i]<0:
            tmp = 0
        else:
            tmp = abs(sum_b+b[i])+1
            b[i] -= tmp
            ans_b += tmp
    sum_b+=b[i]
#print(a)
#print(sum_a)
print(min(ans_a,ans_b))
### BUGGY CODE ###

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

m = 0
t = 0

for i in range(1, n):
    count = A.count(i)
    print(count)
    m += count
    t = i
    if m == n - 1:
        break
for _ in range(t, n):
    print(0)


### FIXED CODE ###

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

# m = 0
# t = 0

# for i in range(1, n):
#     count = A.count(i)
#     print(count)
#     m += count
#     t = i
#     if m == n - 1:
#         break
# for _ in range(t, n):
#     print(0)

B = [0] * n
for i in A:
    B[i-1] += 1
for i in B:
    print(i)
### BUGGY CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,max_c=map(int,readline().split())
    d=[list(map(int,readline().split())) for _ in range(max_c)]
    c=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

    #前処理
    color_table=[[0]*max_c for _ in range(3)]
    for color in range(max_c):
        for i in range(n):
            for j in range(n):
                color_table[(i+j+2)%3][color]+=d[c[i][j]][color]

    #全探索
    ans=float("inf")
    for i in range(max_c):
        for j in range(max_c):
            for k in range(max_c):
                if i==j or j==k or k==i:
                    continue
                ans=min(ans,color_table[0][i]+color_table[1][j]+color_table[2][k])

    print(ans)

if __name__=="__main__":
    main()

### FIXED CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,max_c=map(int,readline().split())
    d=[list(map(int,readline().split())) for _ in range(max_c)]
    c=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

    #前処理
    color_table=[[0]*max_c for _ in range(3)]
    for color in range(max_c):
        for i in range(n):
            for j in range(n):
                color_table[(i+j+2)%3][color]+=d[c[i][j]][color]

    #全探索
    ans=float("inf")
    for i in range(max_c):
        for j in range(max_c):
            for k in range(max_c):
                if i==j or j==k or k==i:
                    continue
                ans=min(ans,color_table[0][i]+color_table[1][j]+color_table[2][k])

    print(ans)

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

import sys
read = sys.stdin.buffer.read

r = 998244353
 
n, s, *As = map(int, read().split())
import copy
answer = 0
f = [0]*3001
for A in As:
    c = copy.deepcopy(f)
    t = [0]*A
    f = t+c
    f = f[:-A]
    f = [x+y for x,y in zip(f,c)]
    f[0] += 1
    f[A] += 1
    answer += f[s]

answer %= r
print(answer)

### FIXED CODE ###

def main():
  import sys
  read = sys.stdin.buffer.read
  r = 998244353
  U, S, *A = map(int, read().split())
  import copy
  ans = 0
  f = [0]*3010
  for a in A:
      c = copy.copy(f)
      f = [0]*a+c[:-a]
      f = [x+y for x,y in zip(f,c)]
      f[0] += 1
      f[a] += 1
      ans += f[S]
  ans %= r
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
S = ''

for i in range(N):
    n = A.index(i+1)
    S += str(n+1) + ' '

print(S.lstrip())

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
O = [0] * N

for i , a  in enumerate(A): #リストAのインデックスiと値a
    O[a-1] = i+1

print(*O)
### BUGGY CODE ###

from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*10000
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

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

n,*a=map(int,open(0).read().split())
dp=[[0]+[-10**18]*n for _ in range(n+1)]
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i+1][j]=max(dp[i-1][j],dp[i-1][j-1]+a,dp[i][j])
print(dp[n][n//2])

### FIXED CODE ###

from collections import*
n,*a=map(int,open(0).read().split())
dp=[defaultdict(lambda:-10**18)for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
x=bisect.bisect_left(A,0,lo=0,hi=len(A))
y=bisect.bisect_right(A,0,lo=0,hi=len(A))
AN=x
A0=y-x
AP=n-y
if x!=0:
  An=A[:x]
else:
  An=[]
Ann=An[::-1]
Annn=[0]*AN
for i in range(AN):
  Annn[i]=Ann[i]*(-1)
if y!=n:
  App=A[-n+y:]
  Ap=App[::-1]
else:
  Ap=[]
if k<=AN*AP:
  ok=An[0]*Ap[0]-1
  ng=0
  while ng-ok>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+AP-bisect.bisect_left(App,((-1)*mid+(-1)*An[i]-1)//((-1)*An[i]),lo=0,hi=AP)
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok+1
  print(ans)
elif k<=n*(n-1)//2-AN*(AN-1)//2-AP*(AP-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1
  if AN>0 and AP>0:
    ok=max(An[0]**2,Ap[0]**2)
  elif AN>0:
    ok=An[0]**2
  else:
    ok=Ap[0]**2
  ng=0
  while ok-ng>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+max(0,AN-i-1-bisect.bisect_left(Annn,(mid+Annn[AN-i-1]-1)//Annn[AN-i-1],lo=0,hi=AN))
    for i in range(AP):
      c=c+max(0,AP-i-1-bisect.bisect_left(App,(mid+App[AP-i-1]-1)//App[AP-i-1],lo=0,hi=AP))
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok-1
  print(ans)

### FIXED CODE ###

import sys
import bisect
iuput=sys.stdin.readline
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
s=bisect.bisect_left(A,0,lo=0,hi=len(A))
t=bisect.bisect_right(A,0,lo=0,hi=len(A))
An=A[0:s]
Ap=A[t:n]
if k<=s*(n-t):
  #二分探査
  ng=-10**19
  ok=1
  while ok-ng!=1:
    #積がmid以下になる組み合わせの数をカウント
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<n-t:
        while An[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if An[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    if c<k:
      ng=mid
    else:
      ok=mid
  print(ok)
elif k<=n*(n-1)//2-((n-t)*(n-t-1)//2)-s*(s-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1#大きい順にk番目
  Ann=[0]*s
  for i in range(s):
    Ann[i]=An[i]*-1
  Ann=Ann[::-1]
  App=[0]*(n-t)
  for i in range(n-t):
    App[i]=Ap[i]*-1
  App=App[::-1]
  ng=-10**19
  ok=1
  while ok-ng!=1:
    #積がmid以下になる組み合わせの数をカウント
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<s:
        while An[i]*Ann[j]>mid:
          j=j+1
          if j==s:
            break
      if An[i]*Ann[-1]>mid:
        j=s
      c=c+(s-j)
    cc=0
    for i in range(s):
      if An[i]*A[i]*-1<=mid:
        cc=cc+1
    j=0
    for i in range(n-t):
      if j<n-t:
        while App[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if App[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    for i in range(n-t):
      if Ap[i]*Ap[i]*-1<=mid:
        cc=cc+1
    c=(c-cc)//2
    if c<k:
      ng=mid
    else:
      ok=mid
  print(-1*ok)
### BUGGY CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

#/usr/bin/python3
n = int(input())
list_a = list(map(int, input().split()))
result = 1
#if 0 in list_a:
#        print(0)
#        exit()
  
for i in range(n):
    result *= int(list_a[i])
if result > 10**18:
	print("-1")
else:
  print(result)

### FIXED CODE ###

#/usr/bin/python3
n = int(input())
list_a = list(map(int, input().split()))
result = 1
if 0 in list_a:
        print(0)
        exit()
  
for i in range(n):
    result *= int(list_a[i])
    if result > 10**18:
        print("-1")
        exit()
print(result)
### BUGGY CODE ###

n = int(input())
d_l = list(map(int,input().split()))

count_dict = {}
for i in range(n):
    count_dict[i] = 0
for val in d_l:
    count_dict[val] += 1

if d_l[0] != 0 or count_dict[0] != 1:
    ans = 0
else:
    ans = 1

for i in range(1,n):
    ans = ans*(count_dict[i-1]**count_dict[i])
    if ans == 0:
        break

print(ans%998244353)

### FIXED CODE ###

n = int(input())
d_l = list(map(int,input().split()))

count_dict = {}
for i in range(n):
    count_dict[i] = 0
for val in d_l:
    count_dict[val] += 1

if d_l[0] != 0 or count_dict[0] != 1:
    ans = 0
else:
    ans = 1

for i in range(1,n):
    ans = (ans*(count_dict[i-1]**count_dict[i])) %998244353
    if ans == 0:
        break

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

def encode(s):
    val = 0
    min_val = 0
    for c in s:
        if c == '(':
            val += 1
        else:
            val -= 1
            min_val = min(min_val, val)
    return [min_val, val]

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0:
            return False
        h += p[1]
    return True


n = int(input())
ls = []
rs = []
l_total = 0
r_total = 0
for _ in range(n):
    si = encode(input())
    if si[1] > 0:
        ls.append(si)
        l_total += si[1]
    else:
        si[0] -= si[1]
        si[1] *= -1
        rs.append(si)
        r_total += si[1]
list.sort(ls, reverse=True)
list.sort(rs, reverse=True)
if check(ls) and check(rs) and l_total == r_total:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

def encode(s):
    val = 0
    min_val = 0
    for c in s:
        if c == '(':
            val += 1
        else:
            val -= 1
            min_val = min(min_val, val)
    return [min_val, val]

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0:
            return False
        h += p[1]
    return True


n = int(input())
ls = []
rs = []
l_total = 0
r_total = 0
for _ in range(n):
    si = encode(input())
    if si[1] > 0:
        ls.append(si)
        l_total += si[1]
    else:
        si[0] -= si[1]
        si[1] *= -1
        rs.append(si)
        r_total += si[1]
list.sort(ls, reverse=True)
list.sort(rs, reverse=True)
if check(ls) and check(rs) and l_total == r_total:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import itertools
import copy

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

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数

def funct(a,b):
    return (a+b)%mod

for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW,funct))
    NEXT=copy.copy(NOWSUM)
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]-=NOWSUM[j-a-1]


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

### FIXED CODE ###

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

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, a, b, c = [int(i) for i in input().split()]
L = [int(input()) for i in range(n)]

INF = 10 ** 9

def dfs(i, L, A):
    if all(a == 0 for a in A):
        return 0
    if n - L.count(0) < 3:
        return INF
    if i == n:
        return INF
    if L[i] == 0:
        return dfs(i+1, L[:], A[:])
    for j, a in enumerate(A):
        if a == L[i]:
            A[j] = 0
            return dfs(i+1, L[:], A[:])

    res = dfs(i+1, L[:], A[:])
    for j, a in enumerate(A):
        if a == 0:
            continue
        TL = L[:]
        TL[i] = a
        TA = A[:]
        TA[j] = 0
        d = abs(L[i] - a)
        res = min(res, dfs(i+1, TL, TA) + d)

    if L[i] > max(A):
        return res
    for j in range(i+1, n):
        if L[j] == 0:
            continue
        TL = L[:]
        TL[i] += TL[j]
        TL[j] = 0
        res = min(res, dfs(i, TL, A[:]) + 10)

    return res

print(dfs(0, L[:], [a, b, c]))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

N, A, B, C = [int(i) for i in input().split()]
L = [int(input()) for i in range(N)]

INF = 10 ** 9

def dfs(n, a, b, c):
    if n == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a, b, c) > 0 else INF
    res = dfs(n+1, a+L[n], b, c) + 10
    res = min(res, dfs(n+1, a, b+L[n], c) + 10)
    res = min(res, dfs(n+1, a, b, c+L[n]) + 10)
    res = min(res, dfs(n+1, a,  b, c))

    return res

print(dfs(0, 0, 0, 0))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
maxi = max(a)
for i in range(n):
  if a[i] == maxi:
    b = []
    b += a
    b.sort()
    print(b[-2])
  else:
    print(maxi)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
b = []
b += a
b.sort()
if b[-1] == b[-2]:
  maxi = max(a)
  for i in range(n):
    print(maxi)
else:
  maxi = max(a)
  for i in range(n):
    if a[i] != maxi:
      print(maxi)
    else:
      print(b[-2])
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from itertools import combinations

n,x,y=map(int,readline().split())
dis=[0]*n
lst=list(range(1,n+1))
for a,b in combinations(lst,2):
  if b<=x or a>=y:
    dist=b-a
  else:
    dist=min(b-a, abs(x-a)+abs(y-b)+1,abs(y-a)+abs(x-b)+1)
  dis[dist]+=1
print(*dis[1:],sep='\n')


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from itertools import combinations

n,x,y=map(int,readline().split())
dis=[0]*n
lst=list(range(1,n+1))
for a,b in combinations(lst,2):
  if b<=x or a>=y:
    dist=b-a
  else:
    dist=min(b-a, abs(x-a)+abs(y-b)+1)
  dis[dist]+=1
print(*dis[1:],sep='\n')
### BUGGY CODE ###

n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    total = T+A
    x = -(-total//(a+t))
    for x in range(x, 10**15):
        if T <= t*x and A <= a*x:
            T = t*x
            A = a*x
            break

print(T+A)

### FIXED CODE ###

n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    total = T+A
    x = -(-total//(a+t))
    x = max(x, -(-T//t))
    x = max(x, -(-A//a))
    T = t*x
    A = a*x

print(T+A)
### BUGGY CODE ###

import sys
from numba import njit

@njit(cache=True)
def solve(a,n):
    ava = [0]*a[-1]
    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))

### FIXED CODE ###

import sys

def solve(a,n):
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]:
            for i in range(2*rep,m,rep):
                ava[i] += 2
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))
### BUGGY CODE ###

s=input()
n=len(s)

dp=[[0]*13 for i in range(n)]

if s[0]!='?':
    a=int(s[0])*10**(n-1)%13
    dp[0][a]=1
else:
    for k in range(10):
        a=k*10**(n-1)%13
        dp[0][a]=1

for i in range(1,n):
    m=10**(n-i-1)%13
    if s[i]!='?':
        for j in range(13):
            dp[i][j]=dp[i-1][(j-int(s[i])*m)%13]
    else:
        for k in range(10):
            for j in range(13):
                dp[i][j]+=dp[i-1][(j-k*m)%13]
print(dp[n-1][5]%(10**9+7))

### FIXED CODE ###

s=input()
n=len(s)
p=10**9+7
 
dp=[[0]*13 for i in range(n)]
m=[0]*(n-1)+[1]
for i in range(n-1):
    m[-i-2]=m[-i-1]*10%13
 
if s[0]!='?':
    a=int(s[0])*m[0]%13
    dp[0][a]=1
else:
    for k in range(10):
        a=k*m[0]%13
        dp[0][a]=1
 
for i in range(1,n):
    if s[i]!='?':
        for j in range(13):
            dp[i][j]=dp[i-1][(j-int(s[i])*m[i])%13]%p
    else:
        for k in range(10):
            for j in range(13):
                dp[i][j]+=dp[i-1][(j-k*m[i])%13]%p
print(dp[n-1][5]%p)