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

from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    stack = deque(paths[i]) if i in paths.keys() else []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in stack:
                stack.append(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    if i in paths.keys():
        stack = deque(paths[i])
        cluster = set([i]+paths[i])
    else:
        stack = []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in cluster:
                stack.append(k)
                cluster.add(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
sl = input()
if sl[0] == "V":
    quit()
while left < right:
    mid = (left + right) // 2
    print(mid)
    sm = input()
    if sm[0] == "V":
        quit()

    if (mid - left + 1) % 2 == 1 and sm != sl:
        right = mid - 1
        continue
    elif (mid - left + 1) % 2 == 0 and sm == sl:
        right = mid - 1
    else:
        left = mid + 1


### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

# ABC129D - Lamp
import sys
input = sys.stdin.readline

def main():
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    # T = tuple(zip(*S))  # slice S vertically
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] == 0
            else:
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1
    for i in range(H):
        for j in range(W - 1, -1, -1):
            if S[i][j] == "#":
                R[i][j] == 0
            else:
                if j == W - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                U[i][j] == 0
            else:
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1
    for i in range(H - 1, -1, -1):
        for j in range(W):
            if S[i][j] == "#":
                D[i][j] == 0
            else:
                if i == H - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1

    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC129D - Lamp
import sys
input = sys.stdin.readline

def main():
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] == 0
                U[i][j] == 0
            else:
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            if S[i][j] == "#":
                R[i][j] == 0
                D[i][j] == 0
            else:
                if j == W - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

                if i == H - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


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

#!/usr/bin/env python3
import sys


def solve(S: str):
    sl = [int(S[i]) for i in range(len(S))]
    ct = 0
    for i in range(len(S)):
        crt = sl[i]
        for j in range(i, len(S)):
            if i != j:
                crt *= 10
                crt += sl[j]
            # s = S[i:(j+1)]
            # si = int(s)
            if crt % 2019 == 0:
                ct += 1
    print(ct)
    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()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    T = [0 for _ in range(len(S) + 1)]
    for i in range(len(S) - 1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * pow(10, len(S) - 1 - i, 2019)) % 2019
    # T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [0 for _ in range(2019)]
    # M = [T.count(i) for i in range(2019)]
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    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()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])



### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### BUGGY CODE ###

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

# In[9]:


N,M = map(int, input().split())
alist = []
for _ in range(M):
    alist.append(int(input()))


# In[12]:


dp = [0]*(N+1)
dp[0] = 1
ans = 0
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        dp[i] = dp[i-1] + dp[i-2]
        if i in alist:
            dp[i] = 0
    ans = dp[-1]%1000000007
print(ans)


# In[ ]:






### FIXED CODE ###

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

# In[15]:


from collections import deque


# In[38]:


N,M = map(int, input().split())
alist = [False]*N
for _ in range(M):
    alist[int(input())-1] = True


# In[41]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 10**9+7
if N == 1:
    ans = 1
else:
    if alist[0]:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        if alist[i-1]:
            dp.append(0)
        else:
            dp.append((dp[0]+dp[1])%mod)
        dp.popleft()
    ans = dp[-1]
print(ans)


# In[ ]:
### BUGGY CODE ###

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

cdm = list(filter(lambda x: x%c == 0 or x%d == 0, a_b))

print(len(a_b)-len(cdm))

### FIXED CODE ###

def lcm(a,b):
    ab = a*b
    while b != 0:
        a, b = b, a%b
    return ab //a

def su(n,c,d):
    return n - n//c - n//d + n//lcm(c,d)
    
def main():
    a,b,c,d = map(int,input().split())
    print(su(b,c,d) - su(a-1,c,d))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        if d != a[i]:
            print(-1)
            return
        for j in range(i+1,n):
            que = []
            d = [10**15 for _ in range(n)]
            d[i] = 0
            heappush( que,(0,i) )
            while que:
                p =  heappop(que)
                v = p[1]
                if d[v] < p[0]:
                    continue
                for k in range(len(g[v])):
                    edge = g[v][k]
                    if (edge[0], v) == (i,j) or (edge[0], v) == (j,i):
                        continue
                    if d[edge[0]] > d[v] + edge[1]:
                        d[edge[0]] = d[v] + edge[1]
                        heappush( que,(d[edge[0]] , edge[0]) )
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

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

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(K):
  x = queue.pop(0)
  
  if x % 10 != 0:
    queue.append(10 * x + (x % 10) - 1)
    
  queue.append((10 * x) + x % 10)
    
  if x % 10 != 9:
    queue.append(10 * x + (x % 10) + 1)
    
print(x)

### FIXED CODE ###

from collections import deque
K = int(input())
queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for i in range(K):
  x = queue.popleft()
  
  if x % 10 != 0:
    queue.append(10 * x + (x % 10) - 1)
    
  queue.append((10 * x) + x % 10)
    
  if x % 10 != 9:
    queue.append(10 * x + (x % 10) + 1)
    
print(x)
### BUGGY CODE ###

from collections import Counter
N = int(input())
cnt = Counter(map(int, input().split()))

L = sum([[a for _ in range(min(2, c // 2))] for a, c in cnt.items()], [])
L.sort()

ans = 0 if len(L) < 2 else L[-1] * L[-2]
print(ans)


### FIXED CODE ###

from collections import Counter

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

cntA = Counter(A)
B = []
for a, c in cntA.items():
    if c // 2 == 0:
        continue
    for _ in range(c // 2):
        B.append(a)

B.sort(reverse=True)
ans = B[0] * B[1] if len(B) >= 2 else 0

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

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

### FIXED CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)
### BUGGY CODE ###

N = int(input())
li = list(map(int,input().split()))
A = 1
for i in range (N):
  A = A * li[i]
  i += 1
if A <= 1000000000000000000:
    print(A)
else: 
    print (-1)

### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))
A = 1
i = 0
B = 0
if 0 in li:
  print(0)
else:
    for i in range (N):
      A = A * li[i]
      if (A > 10**18):
        break
      else: 
        B += 1
        i += 1
    if B == N:
      print (A)
    else:
      print (-1)
### BUGGY CODE ###

s = input()
countRemainder = [0] * 2019
cnt = 0

for i in range(len(s)):
    countRemainder[int(s[i:]) % 2019] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

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

def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
            if t in comparing:
                return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (999999999999999967, 999999999999999989)))


### FIXED CODE ###

def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

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

ans = 1
for num in A:
    ans *= num

print(ans if ans <= 10 ** 18 else -1)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

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

if 0 in A:
    print(0)
    exit()
    
upto = 10 ** 18
ans = 1
for num in A:
    ans *= num
    if ans > upto:
        print("-1")
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
lis = []

for i in a:
  if i in lis:
    a.remove(i)
  else:
    a.append(i)
    
print(len(lis))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
dict = {}
count = 0
for i in a:
  if i not in dict:
    dict[i] = 1
  elif i in dict:
    dict[i]+= 1

for i in set(a):
  if dict[i]%2!=0:
    count += 1
    
    
print(count)
### BUGGY CODE ###

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

prod = [1] * (n + 1)
prod[1] = A[0]
for i in range(2, n + 1):
    prod[i] = prod[i - 1] * A[i - 1]

pre_score = prod[k]

for i in range(k + 1, n + 1):
    score = prod[i] // prod[i - k]
    if score > pre_score:
        print('Yes')
    else:
        print('No')
    pre_score = score


### FIXED CODE ###

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

for i in range(k, n):
    if A[i] > A[i - k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]
 
rev_flag = 0
 
for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                S = Query[i][2] + S
            elif rev_flag == 1:
                S = S + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                S = Query[i][2] + S
            elif rev_flag == 0:
                S = S + Query[i][2]
 
if rev_flag == 1:
    S = S[::-1]
 
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

rev_flag = 0

bef = ''
aft = ''

for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                bef = Query[i][2] + bef
            elif rev_flag == 1:
                aft = aft + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                bef = Query[i][2] + bef
            elif rev_flag == 0:
                aft = aft + Query[i][2]

S = bef + S + aft
if rev_flag == 1:
    S = S[::-1]

print(S)
### BUGGY CODE ###

a,b,k = map(int,input().split())
n = b-a+1
ok = 0
print(a)
while a < b:
    ok += 1
    a += 1
    if k/2 >= n:
        print(a)
    else:
        if ok < k or ok >= n-k:
            print(a)
        
    

### FIXED CODE ###

a,b,k = map(int,input().split())
if k >= (b-a+1)/2:
    for i in range(a,b+1):
        print(i)
        
else:
    for j in range(a,a+k):
        print(j)
    for l in range(b-k+1,b+1):
        print(l)
### BUGGY CODE ###

s = input()

sum = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if int(s[i:j+1])%2019 == 0:
            sum += 1

print(sum)

### FIXED CODE ###

s = input()

res = [0 for i in range(2019)]
res[0] += 1

resten = 1
ressum = int(s[-1])
res[ressum] += 1

for i in range(2, len(s)+1):
    resten = (resten*10)%2019
    ressum = (int(s[-i])*resten + ressum)%2019
    res[ressum] += 1

ans = 0
for i in range(2019):
    ans += res[i]*(res[i]-1)//2
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
  mul = 0
else:
  mul = 1
  for i in range(N):
    mul = mul * A[i]
    if mul > 10**18:
      break
if mul>10**18:
  print(-1)
else:
  print(mul)
### BUGGY CODE ###

import numpy as np

MOD = 1000000007;


def initMod(c):
	a=np.zeros(13,dtype='int64')
	if (c!=-1):
		a[c]=1
	else:
		for i in range(10):a[i]=1
	return a;


s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=initMod(s[0])

for i in range(1,n):
	dp=np.zeros(13*2,dtype='int64')
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=np.zeros(13,dtype='int64')
	if (c==-1):
		for j in range(10):r+=dp[13-j:26-j]
	else:
		r+=dp[13-c:26-c]
print (r[5]%MOD)

### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)