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

import sys
input=sys.stdin.buffer.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

def solve(V,L):
    t=[(0,0)]
    while V>=2**9:
        for v,w in t:
            nv,nw=v+vw[V][0],w+vw[V][1]
            t.append((nv,nw))
        V//=2
    ans=0
    for v,w in t:
        if L>=w:
            ans=max(ans,v+dp[V][L-w])
    return ans

for i in range(int(input())):
    v,L=map(int,input().split())
    print(solve(v,L))


### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

n, k ,q = list(map(int, input().split()))
li = [input() for i in range(q)]
list = []
for j in range(1,n+1):
    L = str(j)
    if li.count(L) > q - k:
        list.append('Yes')
    else:
        list.append('No')
[print(x) for x in list]

### FIXED CODE ###

n, k ,q = list(map(int, input().split()))
listAns = [input() for i in range(q)]
score = [0] * n
count = 0
for j in listAns:
    score[int(j) - 1] += 1
for h in score:
    if h > q - k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

answer = 0

for i in range(N):
    move = 0
    j = i
    while True:
        if j >= N-1:
            break
        if H[j+1] <= H[j]:
            move += 1
            j += 1
        else:
            break
        answer = max(move, answer)

print(answer)

### FIXED CODE ###

import numpy as np


N = int(input())
H = np.array(list(map(int, input().split())))

answer = 0

L1 = (H[:-1] >= H[1:])
#print(L1)

answer = 0
count = 0
for l in L1:
    if l:
        count += 1
    else:
        answer = max(answer, count)
        count = 0

print(max(answer, count))
### BUGGY CODE ###

import math
Q = int(input())


def prime_factorization(num):
    sqrt_num = math.sqrt(num)
    prime_numbers = []
    for i in range(2, int(sqrt_num) + 1):
        # print(num)
        while num % i == 0:
            # print(num)
            num = num / i
            prime_numbers.append(i)
    if num != 1:
        prime_numbers.append(int(num))
    return prime_numbers


for i in range(Q):
    l, r = map(int, input().split())
    count = 0
    for k in range(l, r + 1):
        if k % 2 == 1:
            # print(k)
            if len(prime_factorization(k)) == 1 and len(prime_factorization((k + 1) // 2)) == 1:
                count += 1
    print(count)


### FIXED CODE ###

from itertools import accumulate
INF = float('inf')


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
# これが素数
# print(P)
P = [n for n in P if (n + 1) // 2 in P]
# 自身 + 1 //2 も素数であるもののみに絞る
# print(P)
a = [0] * (N + 1)
for n in P:
    # likenumberは1にする
    a[n] = 1
# 累積和に変換
a = list(accumulate(a))


Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])
### BUGGY CODE ###

def main():
  h, n = map(int, input().split())
  l = []
  for i in range(n):
    a, b = map(int, input().split())
    l.append([a, b])

  dp = [10 ** 9 for i in range(h+1)]

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]


  print(dp[h])

main()


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

from collections import defaultdict
H,W,N = map(int,input().split())
d = defaultdict(lambda:0)
ab = [tuple(map(int,input().split())) for _ in range(N)]
for i in range(N):
    d[ab[i]] = 1

ans = defaultdict(lambda:0)
def count(a,b):
    for dx1 in [-1,0,1]:
        for dy1 in [-1,0,1]:
            x,y = a+dx1,b+dy1
            if 2<=x<H and 2<=y<W:
                n = 0
                for dx2 in [-1,0,1]:
                    for dy2 in [-1,0,1]:
                        n += d[(x+dx2,y+dy2)]
                ans[n] += 1

for i in range(N):
    count(*ab[i])

ans[0] = (H-2)*(W-2)
for i in range(1,10):
    ans[0] -= ans[i]//i
    ans[i] //= i

for i in range(10):
    print(ans[i])

### FIXED CODE ###

from collections import defaultdict
Delta = [-1,0,1]
d = defaultdict(lambda:0)
def paint(d,x,y):
    for dx in Delta:
        for dy in Delta:
            d[(x+dx,y+dy)] += 1
H,W,N = map(int,input().split())
for i in range(N):
    a,b = map(int,input().split())
    paint(d,a,b)
ans = defaultdict(lambda:0)
for x,y in d.keys():
    if 2<=x<=H-1 and 2<=y<=W-1:
        ans[d[(x,y)]] += 1
ans0 = (H-2)*(W-2)
for i in range(10):
    ans0 -= ans[i]
ans[0] = ans0
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [-1] * (N+1)
    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if mark[current] == -1:
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    for s in mark[2:]:
        print(s)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

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

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
cs = [[0] * 60 for _ in range(N + 1)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(60):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[i + 1][j] = (cs[i][j] + x) % mod
res = 0
#print(cs[-1])
#print(cs[2])
for i in range(N):
  t = 0
  for j in range(60):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * ((N - i - 1) - (cs[-1][j] - cs[i + 1][j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * (cs[-1][j] - cs[i + 1][j])
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mxbit = 0
for i in range(N):
  mxbit = max(mxbit, a[i].bit_length())
cs = [0] * mxbit
for i in range(N):
  for j in range(mxbit):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[j] += x
res = 0
#print(cs[-1])
#print(cs)
for i in range(N):
  t = 0
  for j in range(mxbit):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * (N - (cs[j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * cs[j]
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod * pow(2, mod - 2, mod) % mod)
### BUGGY CODE ###

import sys

N = int(input())
As = [int(n) for n in input().split()]

limit = 10**18
over = False

prod = 1
for A in As:
    prod *= A
    if prod > limit:
        over = True
    if prod == 0:
        print(0)
        sys.exit(0)

if over:
    print(-1)
    sys.exit(0)
else:
    print(prod)

### FIXED CODE ###

import sys

N = int(input())

As = [int(n) for n in input().split()]
As_set = set(As)

limit = 10**18

prod = 1

if 0 in As_set:
    print(0)
    sys.exit(0)

over = False
for A in As:
    prod *= A
    if prod > limit:
        print(-1)
        sys.exit(0)

print(prod)
### BUGGY CODE ###

x = int(input())

a = 0
while(True):
    b = x - a ** 5
    b = int(x ** (1 / 5))
    if a ** 5 - b ** 5 == x:
        break
    if a ** 5 - (b*-1)** 5 == x:
        b *= -1
        break
    b = x + a ** 5
    if a ** 5 - b ** 5 == x:
        a *= -1
        break
    if a ** 5 - (b*-1)** 5 == x:
        a *= -1
        b *= -1
        break
    a += 1
print(a, b) 

### FIXED CODE ###

x = int(input())

flg = 'n'
for a in range(-120, 121, 1):
    for b in range(-120, 121, 1):
        if a ** 5 - b ** 5 == x:
            flg = 'y'
            break
    if flg == 'y':
        break
print(a, b)
### BUGGY CODE ###

S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

for i in reversed(range(N)):
    for j in reversed(range(4)):
        if j == 3:
            m = 3 if S[i] == '?' else 1
            dp[i][j] = m * dp[i + 1][j] % MOD
        else:
            m1 = 3 if S[i] == '?' else 1
            m2 = 1 if S[i] == '?' or S[i] == 'ABC'[j] else 0
            dp[i][j] = m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1] % MOD
            
print(dp[0][0] % MOD)




### FIXED CODE ###

S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

for i in reversed(range(N)):
    m = 3 if S[i] == '?' else 1
    for j in reversed(range(3)):
        dp[i][j] = m * dp[i + 1][j]
        if S[i] == '?' or S[i] == 'ABC'[j]:
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= MOD
    
    # j == 3
    dp[i][3] = m * dp[i + 1][3] % MOD
            
print(dp[0][0] % MOD)
### BUGGY CODE ###

A=list(input())
L = len(A)
num = L
while True:
    pre = A[0]
    end = True
    for i in range(1,L):
        if A[i] != pre:
            if i*2 < L and L - i < num:
                num = L - i
            elif i < num:
                num = i
            for j in range(i):
                A[j] = '0' if A[j] == '1' else '1'
            end = False
            break
    if end:
        break
print(num)

### FIXED CODE ###

A=list(map(int,list(input())))
L = len(A)
num = L
pre = A[0]
end = True
for i in range(1,L):
    if A[i] != pre:
        if i*2 < L and L - i < num:
            num = L - i
        elif i < num:
            num = i
    pre = A[i]
print(num)
### BUGGY CODE ###

n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    e = c[0]
    for j in range(len(t[e])):
        if dis[t[e][j]] >= dis[e] +1:
            dis[t[e][j]] = dis[e] +1
            near[t[e][j]] = e
            c.append(t[e][j])
    del c[0]
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)


### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)
### BUGGY CODE ###

from collections import deque
import copy

N,K = map(int,input().split(" "))

V = deque(map(int,input().split(" ")))

def search(N,K,V,score,a,b):
    if a+b < min(N,K):
        Vb = copy.copy(V)
        scoreA = copy.copy(score)
        scoreB=copy.copy(score)
        scoreA.append(V.popleft())
        A = search(N,K,V,scoreA,a+1,b)
        scoreB.append(Vb.pop())
        B = search(N,K,Vb,scoreB,a,b+1)
    score = sorted(score)
    counter = 0
    while(counter < K-a-b):
        if len(score)== 0:
            break;
        if score[0]<0:
            score.pop(0)
            counter +=1
        else:
            break;
    ans = sum(score)
    if a+b < min(N,K):
        return max(0,ans,A,B)
    else:
        return max(0,ans)

score = []
a = 0
b= 0
ans = search(N,K,V,score,a,b)
print(ans)

### FIXED CODE ###

from collections import deque

N,K = map(int,input().split(" "))

V = deque(map(int,input().split(" ")))

def search(N,K,V,score):
    ans = 0
    for i in range(min(N,K)+1):
        for j in range(min(N,K)-i+1):
            score = []
            for a in range(i):#do operation A
                score.append(V[a])
            for b in range(j):#do operation B
                score.append(V[len(V)-b-1])
            score=sorted(score)
            counter = 0

            while(counter < K-i-j):#do operation C,D
                if len(score)== 0:
                    break;
                if score[0]<0:
                    score.pop(0)
                    counter +=1
                else:
                    break;   
            ans = max(ans,sum(score))

    return ans

score = []
ans = search(N,K,V,score)
print(ans)
### BUGGY CODE ###

N = int(input())
moji =[]
for i in range(N):
    a = sorted(input())
    moji.append(''.join(a))

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

print(ans)



### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

N = int(input())
moji =[]
for i in range(N):
    a = sorted(input())
    moji.append(''.join(a))


dic = {}
for i in moji:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

ans = 0
for value in dic.values():
    if value >=2:
        a= C(value, 2)
        ans+=a

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

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())

r = [0]*(n+1)
r[0] = 1
if 1 in a:
  r[1] = 0
else:
  r[1] = 1
for i in range(2, n+1):
  if i in a:
    continue
  else:
    r[i] = (r[i-1] + r[i-2])%1000000007

print(r[n])

### FIXED CODE ###

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())

up = [0]*(m+1)
if m == 0:
  up[0] = n
else:
  up[0] = a[0]-1
  up[m] = n - a[m-1]-1
  for i in range(m-1):
    up[i+1] = a[i+1]-a[i]-2

ans = 1
if -1 in up:
  ans = 0
else:
  f = [0]*(max(up)+1)
  f[0] = 1
  if max(up) > 0:
    f[1] = 1
    for i in range(2, max(up)+1):
      f[i] = f[i-1] + f[i-2]
  for i in range(m+1):
    ans *= f[up[i]]

print(ans % 1000000007)
### BUGGY CODE ###

s = input()
k = int(input())

length = len(s)
sub = []
for item in "abcdefghijklmnopqrstuvwxyz":
  if item in s:
    for i, c in enumerate(s):
      if c == item:
        for j in range(0,length - i + 1):
          if j==0:
            if s[i] not in sub:
              sub.append(s[i])
          else: 
            if s[i:i+j] not in sub:
              sub.append(s[i:i+j])
    if len(sub) >= k:
      break
print(sorted(sub)[k-1])

### FIXED CODE ###

s = input()
k = int(input())

length = len(s)
sub = []
for item in "abcdefghijklmnopqrstuvwxyz":
  if item in s:
    for i, c in enumerate(s):
      if c == item:
        for j in range(0,length - i + 1):
          if j > 5:
            break
          if j==0:
            if s[i] not in sub:
              sub.append(s[i])
          else: 
            if s[i:i+j] not in sub:
              sub.append(s[i:i+j])
    if len(sub) >= k:
      break
print(sorted(sub)[k-1])
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
def gcd(L):
    
    

    while True:
        NL = []
        #print(L)
        rs = 0
        minb = min(L)
        for l in L:
            r = l % minb
            if r != 0:
                NL.append(r)
                rs += r
        NL.append(minb)
        L = NL
        
        if rs == 0:
            return minb

max = 0
for i in range(1,len(A)+1):
    g = gcd(A[0:i-1]+A[i:])
    #print(i,g,(A[0:i-1]+A[i:]))
    if max < g:
        max = g
print(max)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
def gcdaaaaaaaaa(L):
    nextminb = L[0]
    nextn = len(L)
    while True:
        n = nextn
        minb = nextminb
        for l in L[:n]:
            nextn = 0
            r= l % minb
            
            if r != 0:
                L[nextn] = r
                nextn += 1
                if r < nextminb :
                    nextminb = r
        if minb == nextminb:
            return minb
        
def gcd(a,b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b,r)
def gcdL(L):
    g = L[0]
    for l in L:
        g = gcd(g,l)
    return g



lgcd = [0] * N
rgcd = [0] * N

lg = A[0]
rg = A[-1]
for i in range(N):
    
    lg = gcd(lg,A[i])
    lgcd[i] = lg
    rg = gcd(rg,A[N-i-1])
    rgcd[N-i-1] = rg
    
maxg = max(lgcd[N-2],rgcd[1])
for i in range(1,N-1):
    g = gcd(lgcd[i-1],rgcd[i+1])
    if maxg < g:
        maxg = g

print(maxg)
### BUGGY CODE ###

S=input()
N=len(S)
Sinfo=''
for i in range(0,N):
    if S[i]=='?':
        Sinfo+='0'
    else:
        Sinfo+=S[i]
first=int(Sinfo)%13
count=0
hatenadata=[]
for i in range(0,N):
    if S[i]=='?':
        count+=1
        hatenadata.append(i)

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

print(dp[count][5]%(10**9+7))


### FIXED CODE ###

S=input()
N=len(S)
count=0
hatenadata=[]
Sinfo=[]
for i in range(0,N):
    if S[i]=='?':
        Sinfo.append('0')
        count+=1
        hatenadata.append(i)
    else:
        Sinfo.append(S[i])
X=''.join(Sinfo)
first=int(X)%13

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

print(dp[count][5]%(10**9+7))
### BUGGY CODE ###

# C - Exception Handling
N = int(input())
A = [int(input()) for i in range(N)]

#print(A)

for i in range(N):
    tmp = A[i]
    A[i] = 0
    print(max(A))
    A[i] = tmp


### FIXED CODE ###

# C - Exception Handling
N = int(input())
A = [int(input()) for i in range(N)]

#print(A)
max1 = sorted(A, reverse=True)
max2 = max1[0]

for i in range(N):
    if A[i] == max2:
        print(max1[1])

    else:
        print(max2)
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * N for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c

for i in range(N):
    d[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 10 ** 10

for i in itertools.permutations(r):
    dist = 0
    for j in range(R - 1):
        dist += d[i[j]][i[j + 1]]
    ans = min(ans, dist)

print(ans)


### FIXED CODE ###

import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * N for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c

for i in range(N):
    d[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 10 ** 10

for i in itertools.permutations(r):
    dist = 0
    for j in range(R - 1):
        dist += d[i[j]][i[j + 1]]
    ans = min(ans, dist)

print(ans)