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

import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    hq = [1]
    num = [0]*(2**(n+1)+1)
    num[0] = 10**10
    nqi = []
    for i in s:
#        print(hq)
        while hq:
            qi = hpq.heappop(hq)
            if num[qi//2] == i:
                if not hq:
                    print("No")
                    exit()
                nqi.append(qi)
                continue
            ndi = qi*(2**(n-len(str(format(qi,"b")))+1))
            while ndi > qi:
                num[ndi] = i
                hpq.heappush(hq,(ndi//2)*2+1)
                ndi //= 2
            num[qi] = i
            while nqi:
                j = nqi.pop()
                hpq.heappush(hq,j)
            break
    print("Yes")



if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    al = [False]*(2**n)
    al[0] = True
    for i in range(n):
        usd = deque()
        cnt = 2**i
        for j,sj in enumerate(s):
            if al[j]:
                usd.append(sj)
            elif usd[0] > sj:
                usd.popleft()
                al[j] = True
                cnt -= 1
                if not cnt:
                    break
        if cnt != 0:
            print("No")
            exit()
    print("Yes")



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

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
for i in range(2**n):
	bit_i=bin(i)[2:].zfill(n)
	vi=0
	ci=0
	for j in range(len(bit_i)):
		if(bit_i[j]=='1'):
			vi+=v[j]
			ci+=c[j]
	if(ans < vi-ci):
		ans=vi-ci
print(ans)

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
diff=[v[i]-c[i] for i in range(n) if v[i]-c[i] > 0]
diff.append(0)
print(sum(diff))
### BUGGY CODE ###

import sys
import collections

# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    else:
        return b

def main():  
    # 入力
    N, M = map(int, input().split())
    # 隣接関係は隣接リストで管理する
    lst_edge = [[] for _ in range(N)]
    # 各頂点の入力辺の本数
    deg = [0] * N  
    for _ in range(M):
        x, y = map(int, input().split())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1
    
    # 入力辺を持たない頂点をqueueに入れる
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    # 各頂点の最初に入力辺を持たなかった点からの距離
    dp = [0] * N  

    while list(que) != []:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            # エッジ(v, nv)をグラフから削除する
            deg[nv] -= 1
            if deg[nv] == 0:
                # エッジがなくなったことで、入力辺がなくなったらqueueに入れる
                que.append(nv)
                # 最初に入力辺を持たなかった点からの距離
                dp[nv] = chmax(dp[nv], dp[v] + 1)
    
    print(max(dp))


main()

### FIXED CODE ###

import sys

# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    else:
        return b

def main():  
    # 入力
    N, M = map(int, input().split())
    # 隣接関係は隣接リストで管理する
    lst_edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)

    # dp[v] := ノードvを始点とした時の有向パスの長さの最大値
    # -1 未訪問で初期化。
    dp = [-1] * N

    # メモ化再帰
    def rec(v):
        # 既に更新済み
        if dp[v] != -1:
            return dp[v]
        ans = 0
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            ans = chmax(ans, rec(nv) + 1)
        dp[v] = ans
        return dp[v]
    
    # 全ての点に対して更新する
    ans = 0
    for v in range(N):
        ans = chmax(ans, rec(v))
    
    print(ans)



main()
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))

    m = 10 ** 9 + 7
    ans = 0
    a = [i % m for i in a]
    for i in range(n):
        for j in range(i + 1, n):
            ans += a[i] * a[j]
            if ans >= m:
                ans = ans % m
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

### FIXED CODE ###

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)
### BUGGY CODE ###

import sys
def input() -> str:
    return sys.stdin.readline()
m = int(input())
n, s = 0, 0
for i in range(m):
  d, c = [int(i) for i in input().split()]
  n += c
  s += d * c
while s >= 10:
  s -= 9
  n += 1
print(n - 1)

### FIXED CODE ###

import sys
def input() -> str:
    return sys.stdin.readline()
m = int(input())
n, s = 0, 0
for i in range(m):
  d, c = [int(i) for i in input().split()]
  n += c
  s += d * c
print(n + (s - 1) // 9 - 1)
### BUGGY CODE ###

'''catupper
三重ループで大丈夫。関数化することでコードが読みやすくなる。
配列の使い方は基本的。ソートしなくても三重ループでOK。
'''
N=int(input())
L=list(map(int,input().split()))

def ok(A,B,C):
  return A<B+C and B<C+A and C<A+B

ans=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if ok(L[i],L[j],L[k]):
        ans+=1

print(ans)    

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l=sorted(l)
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    idx=bisect.bisect_right(l,l[i]+l[j]-1,j+1)
    ans+=idx-(j+1)
print(ans)
### BUGGY CODE ###

import numpy as np
n, k = tuple(map(int, input().split()))

if k == 0:
    print(n*n)
    exit()
    
ans = 0
for a in range(k, n+1):
    ans += n-a
    b = np.arange(k+1, a-k+1)
    ans += np.sum((a%b)>=k)

print(ans)

### FIXED CODE ###

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

ans = 0
for b in range(max(1, k), n+1):
    ans += (b-k)*(n//b)
    if n%b >= k and k>0:
        ans += n%b-k+1
    elif n%b >= k:
        ans += n%b
print(ans)
### BUGGY CODE ###

import math
N=int(input())
total=[]
candi=[]

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      l=math.gcd(i,j)
      ans=math.gcd(l,k)
      total.append(ans)
      

print(sum(total))

### FIXED CODE ###

from math import gcd
N=int(input())
total=0

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      total+=gcd(gcd(i,j),k)
      
print(total)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cost = [0,2,5,5,4,5,6,3,7,6]

dp = ["" for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c] == "":
        dp[c] = str(num)
    else:
        dp[c] = str(max(int(dp[c]), num))

for i in range(N+1):
    for num in A:
        c = cost[num]
        prev = dp[i]
        if prev != "":
            if int(prev[0]) > num:
                nxt = prev + str(num)
                nxt_i = int(nxt)
            else:
                nxt = str(num) + prev
                nxt_i = int(nxt)
            if dp[i + c] == "":
                dp[i + c] = nxt
            else:
                dp[i + c] = str(max(int(dp[i + c]), nxt_i))

print(dp[N])


### FIXED CODE ###

import copy

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cost = [0,2,5,5,4,5,6,3,7,6]

dp = [[0 for _ in range(10)] for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c][0] == 0:
        dp[c][0] = 1
        dp[c][num] = 1

for i in range(1, N+1):
    for num in A:
        c = cost[num]
        prev = copy.deepcopy(dp[i])
        if prev[0] != 0:
            if dp[i + c][0] > dp[i][0] + 1:
                continue
            elif dp[i + c][0] == dp[i][0] + 1:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                for number in range(9, 0, -1):
                    if dp[i + c][number] < nxt[number]:
                        dp[i + c] = copy.deepcopy(nxt)
                        break
                    if dp[i + c][number] > nxt[number]:
                        break
            else:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                dp[i + c] = copy.deepcopy(nxt)

# print(dp[N])
ans = ""
for number in range(9, 0, -1):
    for _ in range(dp[N][number]):
        ans = ans + str(number)

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

def main():
  n=int(input())
  a=[0]+list(map(int,input().split()))
  ans=0
  for i in range(1,n):
    if a[i]<n-i:
      for j in range(i+1,n+1):
        if j-i==a[i]+a[j]:
          ans+=1
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import bisect
  n=int(input())
  a=list(map(int,input().split()))
  b=[a[i]+i+1 for i in range(n)]
  c=[i+1-a[i] for i in range(n)]
  b.sort()
  c.sort()
  ans=0
  for i in b:
    x=bisect.bisect_left(c,i)
    y=bisect.bisect_right(c,i)
    z=y-x
    ans+=z
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(input())
a = list(map(int,input().split()))
b = []
for tmp in a:
    b.append(tmp)
    b = list(reversed(b))
b = map(str,b)
print(" ".join(b))

### FIXED CODE ###

# -*- coding:utf-8 -*-
from collections import deque
def odd(num):
    return True if num%2!=0 else False
n = int(input())
a = list(input().split())
b = deque()
for tmp in range(len(a)):
    if odd(n) == odd(tmp+1):
        b.appendleft(a[tmp])
    else:
        b.append(a[tmp])
print(' '.join(b))
### BUGGY CODE ###

# coding: utf-8


def main():
    A, B, K = map(int, input().split())
    for i in range(A, B + 1):
        if i < A + K or B - K < i:
            print(i)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
A, B, K = map(int, input().split())
ans = []
for i in range(K):
    a, b = A + i, B - i
    if a < b:
        ans.extend([a, b])
    elif a == b:
        ans.append(a)
    else:
        break
ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = 0

for i in range(large//2, large):
	if abs(a - i) == abs(b - i):
		ans = i
		break

if ans == 0:
	print("IMPOSSIBLE")
else:
	print(ans)


### FIXED CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = ((a + b) / 2)

if ans.is_integer():
	print(int(ans))
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
#print(a)

prev = 0
now = 1
for i in range(n - (k - 1)):
#    print(i)#
    for j in a[i: k + i]:
#        print(j)#
        now *= j
    if i >= 1:
#        print(prev,now)#
        if prev >= now:
            print("No")
        else:
            print("Yes")
    prev = now
    now = 1

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
#print(a)

for i in range(n - (k - 1)):
    if i >=1:
        if a[i - 1] < a[k+i-1]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(1,(n-i)//2 + 1):
        if i+2*j <= n-1:
            tem = s[i]+s[i+j]+s[i+2*j]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)

### FIXED CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(2, n-i+1, 2):
        if i+j <= n-1:
            tem = [s[i], s[i+j//2], s[i+j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)
### BUGGY CODE ###

A, B, K = map(int, input().split())
ab = [int(i) for i in range(A, B + 1)]
ba = sorted(ab, reverse=True)
ans = []

for i in range(min(K, len(ab))):
    ans.append(ab[i])
    ans.append(ba[i])

ans = sorted(set(ans))
for i in ans:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())

if b-a+1 <= 2*k:
    for num in range(a, b+1):
        print(num)
else:
    for num in range(a, a+k):
        print(num)
    for num in range(b-k+1,b+1):
        print(num)
### BUGGY CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N *= 3
print(dp[2]%INF)

### FIXED CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)

def isOk(T):
    ret = 0
    for a, f in zip(A, F):
        ret += max(0, a - T // f)
    return ret <= K

ok = max(a * f for a, f in zip(A, F))
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

from collections import deque
N = int(input())
A = list(deque(map(int, input().split())) for _ in range(N))
for i in range(N):
    A[i] = deque(map(lambda x: x - 1, A[i]))
# print(A)
ans = 0
change = True
while True:
    change = False
    work = [-1] * N
    for i in range(N):
        if not A[i]:
            continue
        enemy = A[i][0]
        work[i] = enemy
        if work[enemy] == i:
            A[i].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


empty = True
for row in A:
    if row:
        empty = False
if not empty:
    print('-1')
else:
    print(ans)



### FIXED CODE ###

from collections import deque
from pprint import pprint
N = int(input())
nextGame = [deque()] + [deque(map(int , input().split())) for _ in range(N)]
#print(nextGame)

canPlay = [[False] * (N + 1) for _ in range(N + 1)]
#pprint(canPlay)
days = [0] * (N + 1)
que = ([i for i in range(N + 1)])

while que:
    now = que.pop()
    #print("------------------------")
    if not nextGame[now]:
        continue
    enemy = nextGame[now].popleft()
    canPlay[now][enemy] = True
    #print("now : ",now)
    #print("enemy : ",enemy)
    #pprint(canPlay)

    if canPlay[now][enemy] and canPlay[enemy][now]:
        days[now] = days[enemy] = max(days[now], days[enemy]) + 1
        que.append(now)
        que.append(enemy)
    #print("days : ",days)

for test in nextGame:
    if test:
        print("-1")
        exit(0)
print(max(days))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2*1000000)

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

#dp_dict = {}


def dp(i, j):
    #print(i, j)
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i-1)//2:
        return (-1*1000000000)
    if j == 1:
        return A[i]
    # if (i, j) in dp_dict:
        # return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        #dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

### FIXED CODE ###

N = int(input())
A = [0]+list(map(int, input().split(" ")))

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

print(dp_list[-1][N//2])
### BUGGY CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if p>=q:
			break
		if [i,j]==black[p]:
			p+=1
			if i!=0 and field[i-1][j]==False:
				field[i-1][j]=True
				black_new.append([i-1,j])
				new=True
			if i!=h-1 and field[i+1][j]==False:
				field[i+1][j]=True
				black_new.append([i+1,j])
				new=True
			if j!=0 and field[i][j-1]==False:
				field[i][j-1]=True
				black_new.append([i,j-1])
				new=True
			if j!=w-1 and field[i][j+1]==False:
				field[i][j+1]=True
				black_new.append([i,j+1])
				new=True
	black=black_new
	ans+=1
print(ans-1)




### FIXED CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)
### BUGGY CODE ###

# とても時間がかかる

def main():
    n = int(input())
    numlist = []
    for _ in range(n):
        numlist.append(int(input()))

    maxprofit = numlist[1] - numlist[0]
    for i in range(n-1):
        x = max(numlist[i+1:n])
        y = min(numlist[0:i+1])
        if maxprofit < x - y:
            maxprofit = x - y
    print(maxprofit)


if __name__ == '__main__':
    main()



### FIXED CODE ###

n = int(input())
a0 = int(input())
a1 = int(input())
max_profit = a1 - a0
min_i = min(a1, a0)
for i in range(n-2):
    c=int(input())
    if c - min_i > max_profit:
        max_profit = c - min_i
    min_i = min(min_i, c)
print(max_profit)
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

#from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
#from operator import mul,itemgetter
#from bisect import* #bisect_left bisect_right
#from heapq import* #heapify heappop heappushpop
#from math import factorial,pi
#from copy import deepcopy
#import sys
#sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[int(str(i)+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[(10*i+r)%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
if __name__ == '__main__':
    main()