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

N, M = map(int, input().split())
a = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]

X.sort(key=lambda x: x[1], reverse=True)
a.sort()

for b, c in X:
  cnt = 0
  for i in range(N):
    if a[i] < c and cnt < b:
      a[i] = c
      cnt += 1
print(sum(a))

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

X = [list(map(int, input().split())) for _ in range(M)]
X.sort(key=lambda x: x[1], reverse=True)
num_cnt = [x[0] for x in X]
val_cnt = [x[1] for x in X]

idx = 0
cnt = 0
ans = 0
cum = 0
for i in range(min(N, sum(num_cnt))):
  if val_cnt[idx] <= a[i]:
    print(sum(a[i:]) + ans)
    break
  ans += val_cnt[idx]
  cnt += 1
  cum += 1
  if num_cnt[idx] == cnt:
    idx += 1
    cnt = 0
  if cum == N:
    print(ans)
    break
else:
  print(sum(a[sum(num_cnt):] + [val_cnt[i] * num_cnt[i] for i in range(M)]))
### BUGGY CODE ###

N, M = map(int, input().split())

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

D=[]
for i in range(M):
    B, C = map(int, input().split())
    D += [C]*B

A += D
A.sort(reverse = True)

print(sum(A[:N])) 

### FIXED CODE ###

N, M = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))

cnt = 0
ans = 0
a = 0
b = 0
while True:
    if b <= M-1 and A[a] <= B[b][1]:
        n = min(B[b][0], N-cnt)
        ans += B[b][1]*n
        cnt += n
        if cnt == N:
            print(ans)
            break
        b += 1
    elif a <= N-1:
        cnt += 1
        ans += A[a]
        if cnt == N:
            print(ans)
            break
        a += 1
### BUGGY CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


def calc(d,c):
    global zan
    if c == 1:
        zan.append(d)
        return 0
    elif c%2 == 0:
        if d == 0:
            return c
        elif d <= 4:
            return calc(d*2,c//2)+1*(c//2)
        else:
            return calc(d*2-9,c//2)+2*(c//2)
    else:
        zan.append(d)
        return calc(d,c-1)


ans = 0
M = inp()
zan_all = []
for m in range(M):
    d,c = inpl()
    zan = []
    ans += calc(d,c)
    zan.reverse()
    zan_all += zan

for i in range(1,len(zan_all)):
    d = zan_all[i] + zan_all[i-1]
    if d >= 10:
        zan_all[i] = d - 10 + 1
        ans += 2
    else:
        zan_all[i]   = d
        ans += 1

print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


ans = 0
M = inp()
zan = []
for m in range(M):
    d,c = inpl()

    while True:
        if c == 1:
            zan.append(d)
            break
        elif c%2 == 0:
            if d == 0:
                ans += c
                break
            elif d <= 4:
                ans += c//2
                d *= 2
                c //= 2
            else:
                ans += c
                d = d*2 - 9
                c //= 2
        else:
            zan.append(d)
            c -= 1

zan.reverse()

bx = zan[0]
for x in zan[1:]:
    d = x + bx
    if d >= 10:
        bx = d - 10 + 1
        ans += 2
    else:
        bx = d
        ans += 1

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

n , k , q = map(int, input().split())
a = [int(input()) for i in range(q)]
points = [k - q for i in range(n)]
for i in range(n):
    points[i] += a.count(i+1)
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n , k , q = map(int, input().split())
points = [k - q] * n
for i in range(q):
    c = int(input())
    points[c-1] += 1
for i in range(n):
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
c=set(a)
count=0
for i in c:
    w=a.count(i)
    if w!=i:
        if i<w:
            count+=w-i
        else:
            count+=w
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
counter=Counter(map(int,input().split()))
sum=0
for a,cnt in counter.items():
    if cnt<a:
        sum+=cnt
    else:
        sum+=cnt-a
print(sum)
### BUGGY CODE ###

mod = 10**9+7
n,m = map(int,input().split())
lst = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
for i in range(1,n+1):
    if i in lst:
        continue
    elif i==1:
        dp[i] = 1
    elif i==2:
        dp[i] = dp[1]+1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[n])

### FIXED CODE ###

mod = 1000000007
N,M = list(map(int,input().split()))

b = [0]*(N+2)
b[0]=1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
print(b[N]%mod)
### BUGGY CODE ###

import numpy as np
from itertools import product

h, w = map(int, input().split())
s = np.full((h, w), 'x', dtype='U1')
for i in range(h):
    s[i] = list(input())

d = np.full((h*w, w*h), float('inf'))
for i in range(h * w):
    d[i, i] = 0

for i, k in product(range(h), range(w)):
    if s[i, k] == '#':
        continue
    for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0)):
        y, x = i + dy, k + dx
        if y < 0 or h <= y or x < 0 or w <= x or s[y, x] == '#':
            continue
        d[i*w+k, y*w+x] = 1
        d[y*w+x, i*w+k] = 1

# warshall-floyd
for k, i, j in product(range(h * w), repeat=3):
    d[i, j] = min(d[i, j], d[i, k] + d[k, j])

print(d.astype('i8').max())


### FIXED CODE ###

import numpy as np
from collections import deque
from itertools import product

H, W = map(int, input().split())
S = np.full((H, W), 'x', dtype='U1')
for i in range(H):
    S[i] = list(input())

def bfs(x, y):
    dist = np.full((H, W), -1, dtype='i8')
    que = deque()

    dist[x, y] = 0
    que.append((x, y))

    while que:
        h, w = que.popleft()
        d = dist[h, w]
        for dx, dy in ((0, -1), (-1, 0), (1, 0), (0, 1)):
            hh, ww = h + dx, w + dy
            if hh < 0 or H <= hh or ww < 0 or W <= ww or S[hh, ww] == '#' or dist[hh, ww] != -1:
                continue
            dist[hh, ww] = d + 1
            que.append((hh, ww))

    return d

res = 0
for i, k in product(range(H), range(W)):
    if S[i, k] == '#':
        continue
    d = bfs(i, k)
    if d > res:
        res = d
print(res)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 8

output:
390625
"""

import sys


def mod_pow(x, n, _mod):
    res = 1
    while n > 0:
        # check n is odd number
        if n % 2:
            res = res * x % _mod
        x = pow(x, 2) % _mod
        n //= 1
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    M = 1000000007
    # print(pow(n1, n2, M))
    print(mod_pow(n1, n2, M))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 8

output:
390625
"""

import sys


def mod_pow(x, n, _mod):
    res = 1
    while n > 0:
        # check n is odd number
        if n % 2:
            res = res * x % _mod
        x = pow(x, 2) % _mod
        n //= 2
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    M = 1000000007
    # print(pow(n1, n2, M))
    print(mod_pow(n1, n2, M))
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
S = input()
T = input()

def gcd(a, b):
    while b :
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

L = lcm(N, M)
X = ["A" for i in range(L)]

for i in range(N):
    index = i * (L // N)
    X[index] = S[i]

for i in range(M):
    index = i * (L // M) 
    if X[index] != "A" and X[index] != T[i]:
        print(-1)
        sys.exit()
    
print(L)


### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()

def gcd(a, b):
    while b :
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
print(L)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,n=LI()

  # right=n
  # ans=math.floor(a*right/b)-a*math.floor(right/b)
  # left=0
  # while left<=right:
  #   half=(left+right)//2
  #   _ans=math.floor(a*half/b)-a*math.floor(half/b)
  #   if _ans==ans:
  #     return ans
  #   elif _ans>ans:
  #     right=half-1
  #     ans=_ans
  #   else:
  #     left=half+1

  ans=math.floor(a*1/b)-a*math.floor(1/b)
  for i in range(int(math.sqrt(n)),n+1):
    ans=max(ans,math.floor(a*i/b)-a*math.floor(i/b))
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # floor(x/b)がギリギリ割り切れない辺りが一番大きくなりそう
  # -> 実験してみるとmath.floor(a*x/b)-a*math.floor(x/b)はループしてそう
  # -> 答えはfloor(x/b)がギリギリ割り切れないときの値に決め打つぜ！
  a,b,n=LI()
  x=min(n,b-1)
  return math.floor(a*x/b)-a*math.floor(x/b)

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

def mips():
    return map(int,input().split())
def chmin(DP,b,i):
    if (DP[i]> b):
        DP[i] = b
        return True
    return False
N,K = mips()
H = [i for i in mips()]
dp = [10**10 for i in range(N)]
dp[0] = 0
for i in range(1,N):
    for k in range(1,K+1):
        if i-k < 0:
            break
        chmin(dp,dp[i-k]+abs(H[i]-H[i-k]),i)
print(dp[-1])

### FIXED CODE ###

def mips():
    return map(int,input().split())
def chmin(DP,b,i):
    if (DP[i]> b):
        DP[i] = b
        return True
    return False
N,K = mips()
H = [i for i in mips()]
dp = [10**10 for i in range(N)]
dp[0] = 0
for i in range(1,N):
    for k in range(1,K+1):
        if i-k < 0:
            break
        chmin(dp,dp[i-k]+abs(H[i]-H[i-k]),i)
print(dp[-1])
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from functools import lru_cache

def resolve():
    T = int(input())

    @lru_cache
    def f(x, i):
        if i == N:
            return "1" if x else "0"

        ans = f(x, i+1)
        if S[i] == ans:
            return ans
        return f(x^A[i], i+1)

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        if S[-1] == "1":
            ans.append("1")
        else:
            ans.append(f(0, 0))

        f.cache_clear()

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

X = (10**18).bit_length()

def f(a, s, n):
    if s[-1] == "1":
        return 1

    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

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

n = int(input())
ans = 0
for i in range(n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n*(n-1))//2
print(ans)
### BUGGY CODE ###

n  =  int(input())
a= list(input().split())
al = list([int(i) for i in a])
aset = set([int(i) for i in a])

cnt=0

for i in aset:
  #print(i)
  #print(al.count(i-1),al.count(i),al.count(i+1))
  if cnt < al.count(i-1) + al.count(i) + al.count(i+1):
    cnt = al.count(i-1) + al.count(i) + al.count(i+1)
print(cnt)

### FIXED CODE ###

from collections import Counter as C

n  =  int(input())
a= list(input().split())
al = list([int(i) for i in a])
aset = set([int(i) for i in a])

cnt=0
ca = C(al)
#print(C(al)[0])
for i in aset:
  #print(i)
  #print(al.count(i-1),al.count(i),al.count(i+1))
  if cnt < ca[i-1] + ca[i] + ca[i+1]:
    cnt = ca[i-1] + ca[i] + ca[i+1]

print(cnt)
### BUGGY CODE ###

import re

n = int(input())
s = input()
cnt = 0

for i in range(1000):
    tgt = str(i).zfill(3)
    j = 0
    for i in range(n):
        if tgt[j] == s[i]:
            j += 1
        if j == 3:
            cnt += 1
            break
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0

for N in range(1000):
    tgt = str(N).zfill(3)
    if tgt[0] in s:
        i = s.index(tgt[0])
        if tgt[1] in s[i+1:]:
            j = s[i+1:].index(tgt[1]) + i
            if tgt[2] in s[j+2:]:
                cnt += 1
print(cnt)
### BUGGY CODE ###

N, M = list(map(int, input().split(' ')))
result_list = [input().split(' ') for i in range(M)]
AC_total = 0
WA_total = 0
ac_list = []
wa_dict = {}
for p, s in result_list:
    if p not in ac_list:
        if s == 'WA':
            if p in wa_dict:
                wa_dict[p] += 1
            else:
                wa_dict[p] = 1
        else:
            AC_total += 1
            ac_list.append(p)
for p in wa_dict:
    if p in ac_list:
        WA_total += wa_dict[p]
print('{} {}'.format(AC_total, WA_total))

### FIXED CODE ###

N, M = list(map(int, input().split(' ')))
AC_total = 0
WA_total = 0
ac_list = [False] * N
wa_list = [0] * N
for i in range(M):
    p, s = input().split(' ')
    p = int(p) - 1
    if not ac_list[p]:
        if s == 'WA':
            wa_list[p] += 1
        else:
            AC_total += 1
            WA_total += wa_list[p]
            ac_list[p] = True
print('{} {}'.format(AC_total, WA_total))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
total = 1
for i in range(N):
  total *= A[i]
if total > 1e18:
  print(-1)
else:
  print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
total = 1
if 0 in A:
  print(0)
  exit()
for i in range(N):
  total *= A[i]
  if total > 1e18:
    print(-1)
    exit()
print(total)
### BUGGY CODE ###

S = input()
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
for q in query:
  if q == 1:
    S = S[::-1]
  else:
    if q[0] == 1:
      S = q[1] + S
    else:
      S = S + q[1]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
ds = deque(S)
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      ds.extendleft(q[1])
    else:
      ds.extend(q[1])
jds = "".join(ds)
if eo == -1:
  jds = jds[::-1]
print(jds)
### BUGGY CODE ###

n,q = map(int,raw_input().split())
Ai = 2**31-1
A = [Ai]*n
for i in xrange(q):
    com,xi,yi = map(int,raw_input().split())
    if com: # find(xi,yi)
        print min(A[xi:yi+1])
    else: # update(xi,yi) 
        A[xi] = yi

### FIXED CODE ###

# coding: utf-8

n, q = map(int,raw_input().split())
A = [(1<<31) - 1 for i in xrange(100000)]
B = [(1<<31) - 1 for i in xrange(101)]
 
def update(i,x):
    if A[i] == (1<<31) - 1:
        A[i] = x
        B[i/1000] = min(x, B[i/1000])
    else:
        A[i] = x
        MIN = (1<<31) - 1
        for j in xrange(i/1000 * 1000, (i/1000 + 1) * 1000):
            if A[j] < MIN:
                MIN = A[j]
        B[i/1000] = MIN
 
def find(s,t):
    MIN = (1<<31) - 1
    if s/1000 == t/1000 or s/1000 + 1 == t/1000:
        for i in xrange(s, t+1):
            if A[i] < MIN:
                MIN = A[i]
    else:
        #left range
        for i in xrange(s, (s/1000 + 1) * 1000):
            if A[i] < MIN:
                MIN = A[i]
        #middle range
        for j in xrange(s/1000 + 1, t/1000):
            if B[j] < MIN:
                MIN = B[j]
         
        #right range
        for i in xrange(t/1000 * 1000, t+1):
            if A[i] < MIN:
                MIN = A[i]
    print MIN   
     
for i in xrange(q):
    com, s, t = map(int,raw_input().split())
    if com: #find
        find(s,t)
    else: #update
        update(s,t)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10 ** 6)

def resolve():
    N, Q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(N-1)]
    px = [list(map(int, input().split())) for _ in range(Q)]

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    # while len(stk):
    #     print(stk, visited)
    #     v = stk.pop()
    #     if not v in visited:
    #         visited.add(v)
    #     if v>0:
    #         cnt[v] += cnt[par]
    #     for i in edge[v]:
    #         if not i in visited:
    #             stk.append(i)
    #     par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**6)

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    print(*cnt)

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

N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N
#F = [A[i][0] - 1 for i in range(N)]

def get_num(i):
    p = P[i]
    if p >= N - 1:
        return -1
    return A[i][p] - 1


def update(mem):
    for i in mem:
        P[i] += 1


def f():
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if P.count(N - 1) == N:
            return t

        for i in range(N):
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1

        update(mem)
        mem = set()

    return -2

print(f())


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N


def get_num(i):
    return A[i][P[i]] - 1


def update(mem, K):
    for i in mem:
        P[i] += 1
        if P[i] == N - 1:
            K.remove(i)


def f():
    K = {i for i in range(N)}
    L = {i for i in range(N)}
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if len(K) == 0:
            return t

        for i in L:
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1
        update(mem, K)
        L = K & mem
        mem.clear()

    return -2

print(f())
### BUGGY CODE ###

S = input()
N = len(S)
mod = 10**9+7
dp = [[0] * N for _ in range(13)]

if S[0] == "?":
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(S[0])][0] = 1
        
for i in range(1, N):
    if S[i] == "?":
        for s in range(10):
            for x in range(13):
                dp[(x*10 + s)%13][i] += dp[x][i-1]
    else:
        for x in range(13):
            dp[(x*10 + int(S[i]))%13][i] += dp[x][i-1] 
    for t in range(13):
        dp[t][i] = dp[t][i]%mod
print(dp[5][N-1])  

### FIXED CODE ###

S = input()
N = len(S)
mod = 10**9+7
dp = [[0] * N for _ in range(13)]

if S[0] == "?":
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(S[0])][0] = 1
        
for i in range(1, N):
    if S[i] == "?":
        for s in range(10):
            for x in range(13):
                dp[(x*10 + s)%13][i] += dp[x][i-1]
    else:
        for x in range(13):
            dp[(x*10 + int(S[i]))%13][i] += dp[x][i-1] 
    for t in range(13):
        dp[t][i] = dp[t][i]%mod
print(dp[5][N-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    INF = 1 << 62
    q = collections.deque([(0, 0, -1)])
    dist = [INF] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if dist[node] < l:
            continue
        dist[node] = l
        prev[node] = pnode
        for nxt in adj[node]:
            if nxt != pnode and dist[nxt] > l + 1:
                q.append((l + 1, nxt, node))
    if any(x is None for x in prev):
        print("No")
        return
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    q = collections.deque([(0, 0, -1)])
    visited = [False] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if visited[node]:
            continue
        visited[node] = True
        prev[node] = pnode
        for nxt in adj[node]:
            if not visited[nxt]:
                q.append((l + 1, nxt, node))
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()