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

from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]
b = deque([])
for i in range(h):
  for j in range(w):
    if s[i][j] == '#':
      s[i][j] = 0
      b.append([i,j])
    if s[i][j] == '.':
      s[i][j] = 1

dh = [1,0,-1,0]
dw = [0,1,0,-1]

def rev(b):
  cnt = 0
  nb = deque([])
  for p in b:
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >=0 and nh < h and nw >=0 and nw < w and s[nh][nw]==1:
        s[nh][nw] = 0
        nb.append([nh,nw])
  return nb
cnt = 0
while sum([sum(x) for x in s]) > 0:
  b = rev(b)
  cnt += 1

print(cnt)    


### FIXED CODE ###

from collections import deque

h,w = list(map(int,input().split()))
m = [[x for x in input()] for _ in range(h)]
next_que = deque([])
for i in range(h):
  for j in range(w):
    if m[i][j] == '#':
      next_que.append([i,j])


dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(next_que):
  cnt = -1
  while next_que:
    cnt += 1
    que = list(next_que)
    next_que = deque([])
    for cur in que:
      #cur = que.popleft()
      for i in range(4):
        nh = cur[0] + dh[i]
        nw = cur[1] + dw[i]
        
        if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
          m[nh][nw] = '#'
          next_que.append([nh,nw])
  
  return cnt



cnt = bfs(next_que) 

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

n=int(input())
a=list(map(int,input().split()))
set_a=list(set(a))
count=0
for i in set_a:
    if i<a.count(i):
        count+=a.count(i)-i
    elif a.count(i)<i:
        count+=a.count(i)
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 ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = 1
for i in range(k):
    b *= a[i]


ans = [b]

for i in range(n-k):
    ans.append(ans[i]//a[i]*a[k+i])

# print(ans)

for i in range(n-k):
    if ans[i] < ans[i+1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

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

s = list(input())
q = int(input())
lines = [list(input().split()) for i in range(q)]

def q1(s):
    for i in range(len(s) // 2):
        s[i],s[-1-i] = s[-1-i],s[i]
    return s

def q2(s, l):
    if int(l[1]) == 1:
        s.insert(0,l[2])
    else:
        s.extend(l[2])
    return s

for l in lines:
    if int(len(l)) == 1:
        q1(s)
    else:
        q2(s, l)

print(*s, sep='')


### FIXED CODE ###

from collections import deque

def check(reverse_cnt, t):

    if reverse_cnt%2 == 0 and t == 1:
        return True
    elif reverse_cnt%2 == 0 and t == 2:
        return False
    elif reverse_cnt%2 == 1 and t == 1:
        return False
    elif reverse_cnt%2 == 1 and t == 2:
        return True

def solve(s, q, qs):
    reverse_cnt = 0

    for item in qs:

        if len(item) == 1:
            # T = 1 文字列を反転
            reverse_cnt += 1
        else:
            # T = 2

            if check(reverse_cnt, int(item[1])):
                # 先頭に追加
                s.appendleft(item[2])

            else:
                # 末尾に追加
                s.append(item[2])


    if reverse_cnt%2 == 1:
        ans = "".join(s)
        ans = ans[::-1]
    else:
        ans = "".join(s)

    return ans

if __name__ == '__main__':

    s = deque() # queue

    str = input()
    q = int(input())
    qs = [list(input().split()) for i in range(q)]

    s.append(str)

    ans = solve(s, q, qs)
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
result = 0
for i in range(N):
    for j in range(i):
        result = result + (A[i]*A[j])%1000000007
result = result % 1000000007
print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 1000000007
ans = 0
res = [A[0]]
for i in range(N-1):
    res.append(res[i]+A[i+1])
for i in range(1,N):
    ans = ans + (A[i]*res[i-1])%mod
ans = ans%mod
print(ans)
### BUGGY CODE ###

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

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C*=10
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

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

N = int(input())
a = list(map(int, input().split()))
remain = 1  # 残す整数
index = 0

if remain not in a:
    print(-1)
    exit()

while remain in a[index:]:
    index = a[index:].index(remain)
    remain += 1

print(N - remain + 1)


### FIXED CODE ###

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

now = 1
for ai in a:
    if ai == now:
        now += 1

if now == 1:
    print(-1)
else:
    print(N - now + 1)
### BUGGY CODE ###

a,b,x = map(int,input().split())
count = 0
for i in range(a ,b + 1):
    if i % x == 0:
        count += 1
    else:
        continue
print(count)



### FIXED CODE ###

a,b,x = map(int,input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

N,M,K=map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sum_A=0
sum_B=0
for i in range(N):
    sum_A +=A[i]
    if sum_A>K:
        del A[i:]
        break
for i in range(M):
    sum_B +=B[i]
    if sum_B>K:
        del B[i:]
        break
while sum(A)+sum(B)>K:
    if A[-1]>B[-1]:
        del A[-1]
    elif A[-1]<B[-1]:
        del B[-1]
    elif A[-1] == B[-1]:
        del A[-1]
        del B[-1]
        if sum(A)+sum(B)<=K:
            A.append(1)
print(len(A)+len(B))

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
 		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###


n=int(input())
a=[int(i) for i in input().split()]
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  t=1<<k
  for i in range(n):
    if a[i]&t:
      x+=1
  c=x*(n-x)*2**k
  ans+=c
print(ans%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 ###

N, M, Q = [int(_) for _ in input().split()]

lr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    l, r = [int(_) for _ in input().split()]
    lr[l][r] += 1

# for i in range(1, N + 1):
#     print(lr[i][1:])
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    ans = 0
    for i in range(p, q + 1):
        for j in range(p, q + 1):
            ans += lr[i][j]
    print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M, Q = [int(_) for _ in input().split()]

lr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    l, r = [int(_) for _ in input().split()]
    lr[l][r] += 1
for i in range(1, N + 1):
    for j in range(1, N + 1):
        lr[i][j] += lr[i][j - 1]

# for i in range(1, N + 1):
#     print(lr[i][1:])
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    ans = 0
    for i in range(p, q + 1):
        ans += lr[i][q] - lr[i][p - 1]
    print(ans)
### BUGGY CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p <= ai * ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        k = lcm[p] - ps[i].get(p, 0)
        prod = (prod * (p ** k)) % mod
    ret = (ret + prod) % mod

print(ret)
        


### FIXED CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

lcmv = 1
for p in lcm:
    lcmv = (lcmv * (p ** lcm[p])) % mod

def inv(p, k):
    k = mod - k - 1
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = (ret * b) % mod
        b = (b * b) % mod
        k //= 2
    return ret

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = (prod * inv(p, ps[i][p])) % mod
    ret = (ret + prod) % mod

print(ret)
### BUGGY CODE ###

from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)


### FIXED CODE ###

import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)
### BUGGY CODE ###

# メモ化再帰ｓ
# def rec(i,j):
#     if dp[i][j] >= 0:
#         return dp[i][j]
#     res = 0
#     if i == n:
#         res = 0
#     elif j < w[i]:
#         res = rec(i+1,j)
#     else:
#         res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
#     dp[i][j] = res
#     return res

# def main():
#     global n,w,v,dp
#     n = int(input())
#     w,v = [0]*n,[0]*n
#     for i in range(n):
#         w[i],v[i] = map(int,input().split())
#     W = int(input())
#     dp = [[-1]*(W+1) for _ in range(n+1)]
#     print(rec(0,W))

# DP
def main():
    global n,w,v,dp
    n,W = map(int,input().split())
    w,v = [0]*(n),[0]*(n)
    for i in range(n):
        w[i],v[i] = map(int,input().split())
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    print(dp[n][W])


if __name__ == '__main__':
    main()

"""
in
4 5
2 3
1 2
3 4
2 2

out
7
"""

### FIXED CODE ###

def main():
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-wv[i][0] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    print(dp[N][W])

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

N=int(input())
A=list(map(int,input().split()))
count=0
B=[A[0]]
for i in range(1,N) :
  if max(B)<A[i] :
    B.append(A[i])
  else :
    B.append(B[i-1])
ans=0
for i in range(N) :
  ans+=B[i]-A[i]
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
B=[A[0]]
for i in range(1,N) :
  if B[i-1]<A[i] :
    B.append(A[i])
  else :
    B.append(B[i-1])
ans=0
for i in range(N) :
  ans+=B[i]-A[i]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
for i in range(1,N*3+3):
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
i = 0
while queue != []:
    i += 1
    hoge = []
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge:
                    hoge.append(s)
    queue = hoge[:]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)
### BUGGY CODE ###

from bisect import bisect_left
from itertools import combinations

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

ans = 0
for e1, e2, e3 in combinations(L, 3):
    if e1 < e2 + e3 and e2 < e1 + e3 and e3 < e1 + e2:
        ans += 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

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

L.sort()
ans = 0

for a in range(N):
    for b in range(a + 1, N):
        c = bisect_left(L, L[a] + L[b])
        ans += c - b - 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        S = S[::-1]
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            S = c + S
        else:
            S = S + c
print(S)

### FIXED CODE ###

from collections import deque

S = input()
d = deque(S)
Q = int(input())
is_order = True
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        is_order = not is_order
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            if is_order:
                d.appendleft(c)
            else:
                d.append(c[::-1]) 
        else:
            if is_order:
                d.append(c)
            else:
                d.appendleft(c[::-1])
if is_order:
    print("".join(d))
else:
    print("".join(reversed(d)))
### BUGGY CODE ###

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

import numpy as np

total=1
for i in range(n):
    total*=a[i]

a=1000_000_000_000_000_000

if total-a>0:
    print(-1)
else:
    print(total)



### FIXED CODE ###

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

if a.count(0)>0:
    print(0)
    exit(0)

total=1
for i in a:
    total *=i

    if total>10**18:
        print(-1)
        exit(0)
    
print(total)
### BUGGY CODE ###

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

n = int(input())
nums = [int(input()) for _ in range(n)]
print(sum(map(is_prime, nums)))

### FIXED CODE ###

def is_prime(num):
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

n = int(input())
nums = [int(input()) for _ in range(n)]
print(sum(map(is_prime, nums)))
### BUGGY CODE ###

m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
import math
def factorial(t):
  ans = 1
  for i in range(1,t+1):
    ans *= i
    ans %= m
  return ans
def cc(x,y):
  xx = factorial(x) % m
  yy = factorial(y) % m
  xy = factorial(x-y) % m
  return xx * inv(yy) * inv(xy) % m
n,a,b,c = map(int,input().split())
d = 100 - c
awin = a * inv(d)
bwin = b * inv(d)
asc = 0
bsc = 0
for i in range(n):
  p = cc(n-1+i,i) * awin**(n-1) * bwin**i * (n+i)
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1+i,i) * awin**i * bwin**(n-1) * (n+i)
  bsc += p
  bsc %= m
sc = asc * awin + bsc * bwin
sc %= m
scn = sc * 100 * inv(d)
scn %= m
print(scn)

### FIXED CODE ###

#18:04
n,a,b,c = map(int,input().split())
mod = 10 ** 9 + 7
def inv(x):
  ans = 1
  now = x
  while now != 1:
    ans *= mod // now + 1
    ans %= mod
    now = now - mod % now
  return ans
p = (a * inv(a+b)) % mod
q = (b * inv(a+b)) % mod
taka = 0
aoki = 0
tcom = 1
acom = 1
for i in range(n):
  taka += tcom * (n+i)
  tcom *= n+i
  tcom *= inv(i+1)
  tcom *= q
  tcom %= mod
  aoki += acom * (n+i)
  acom *= n+i
  acom *= inv(i+1)
  acom *= p
  acom %= mod
for _ in range(n):
  taka *= p
  taka %= mod
  aoki *= q
  aoki %= mod
ans = taka + aoki
ans *= 100
ans *= inv(a+b)
ans %= mod
print(ans)
### BUGGY CODE ###

S=input()
keta=len(S)
import numpy as np
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
  for j in range(13):
    dp[i][j]%=DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])