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

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



Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
    
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)

maxval=len(Asum)-1

tmp=0
cnt=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  for j in range(lenB):
    cnt+=1
    j=tmp+j
    if j>=lenB-1:j=lenB-1
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)


### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
### BUGGY CODE ###

n,w=map(int,input().split())

weight=[]
value=[]

for i in range(n):
    a,b=map(int,input().split())
    weight+=[a]
    value+=[b]

dp=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j<weight[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i])

print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
wi=[]
vi=[]

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
dp=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
  for j in range(w+1):
    if j<wi[i]:
      dp[i+1][j]=dp[i][j]
      
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-wi[i]]+vi[i])
      
print(dp[n][w])
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))


def solve():
    dp = [[0]*(i+3) for i in range(N+1)]
    dp[0][1] = 1
    for i in range(1,N+1):
        for j in range(1,i+2):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+3)//2:])
    return ans
print(solve())

### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())
### BUGGY CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
for i in range(1, 18):
    pcs[2**i] = 1
    pcs[2**i-1] = i
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)
    

### FIXED CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)
### BUGGY CODE ###

import itertools


n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    if c == 'R':
        rgb[0].append(i)
    elif c == 'G':
        rgb[1].append(i)
    else:
        rgb[2].append(i)

comb = len(rgb[0]) * len(rgb[1]) * len(rgb[2])

summ = 0
for i in rgb[0]:
    for j in rgb[1]:
        for k in rgb[2]:
            ii = min(i, j, k)
            kk = max(i, j, k)
            jj = sum([i, j, k]) - ii - kk
            if jj - ii == kk - jj:
                summ += 1

print(comb - summ)

### FIXED CODE ###

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    rgb[(c > 'G') + (c > 'B')].append(i)

exclude = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            exclude += 1
        if jj + d < n and jj + d in rgb[2]:
            exclude += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            exclude += 1

summ = len(rgb[0]) * len(rgb[1]) * len(rgb[2])
print(summ - exclude)
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    for j in range(len(s)):
        if s[j]==t[i]:
            k=dp1[j]
            dp1[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp1[j])

dp2=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            k=dp2[j]
            dp2[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp2[j])

m=max(dp1)
cnt=m
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp2[j]>=m-cnt+1:
        ans=s[j]+ans
        cnt-=1
print(ans)



### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp=[[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1]==t[i-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
m=max(max(dp))
ans=''
for i in range(len(t)-1,-1,-1):
    for j in range(len(s)-1,-1,-1):
        if dp[i+1][j+1]==m and s[j]==t[i]:
            ans=s[j]+ans
            m-=1
            break
print(ans)
### BUGGY CODE ###

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

cnt = 0

for i in range(a, b+1):
    if i%x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

ans = b//x - (a-1)//x

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

n,m=map(int,input().split())
maxi=0
for i in range(1,m+1):
    if m%i==0 and m//i >=n:
        maxi=i
    else:
        continue   
        
print(maxi)
 

### FIXED CODE ###

n,m=map(int,input().split())
maxi=0
import math
num=math.sqrt(m)
nums=math.floor(num)

for i in range(1,nums+1):
    if m%i==0:
        number1=i
        number2=m//i
        #二つの約数について比べる
        #number1<number2
        #m//number1>m//number2
        if m//number1>=n and m//number2>=n:
            maxi=max(number2,maxi)
        elif m//number1>=n and m//number2<n:
            maxi=max(maxi,number1)
        
    else:
        continue
print(maxi)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A in jobs.keys():
            jobs[A] = jobs[A] + [B]
        else:
            jobs[A] = [B]

    profit = 0
    potential_jobs = []

    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in jobs.keys():
            potential_jobs += jobs[elappsed_day]
        if len(potential_jobs) > 0:
            profit += potential_jobs.pop(potential_jobs.index(max(potential_jobs)))
            
    print(profit)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

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

import sys
input = sys.stdin.readline

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]

for a, b in ab:
    graph[a-1].append((b-1, -1))
    graph[b-1].append((a-1, -1))

# print(graph)

stack = [(0, -1)]
visited = [-1]*n

k = 0
while stack:
    node, color = stack.pop()
    visited[node] = 1

    if k < len(graph[node]):
        k = len(graph[node])
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):
        if visited[child] == 1:

            continue
        if child_color == -1:
            if tmp == color:
                tmp += 1
            graph[node][i] = (child, tmp)
            stack.append((child, tmp))
            tmp +=1

print(k)
for a, b in ab:
    print(list(filter(lambda x: x[0]==(b-1), graph[a-1]))[0][1])



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

stack = deque([0])
parent = [None]*n
colors = [0]*n
while stack:
    node = stack.popleft()
    color = 1
    for child in graph[node]:
        if child == parent[node]:
            continue
        parent[child] = node
        if color == colors[node]:
            color += 1
        colors[child] = color
        color += 1
        stack.append(child)

 
k = max(colors)
print(k)
for a, b in ab:
    if (a-1) == parent[b-1]:
        print(colors[b-1])
    else:
        print(colors[a-1])
### BUGGY CODE ###

v,e,s=map(eval,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(eval,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

for j in range(v):
    for i in range(v):
        for (t,d) in edge[i]:
            if dis[t]>dis[i]+d:
                dis[t]=dis[i]+d

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])
            

### FIXED CODE ###

'''
????????£????????????1??????????????????
??\???C++??§????????????????§£?±???????????????????????????????????????§???
??????python??§??????????????????Accept??§??????????????????
????????£??¨optimization??????????????§??????
??§????????????Wrong Answer??§?????????
???????????????????????????????????????????????????
Online Judge???????????????Public Solutions??§
????????????nanae?????????python3????????????????????????
????????£??¨?????????????????????
???????????????????????????0.06?§????????????§??????
'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))


while(not q.empty()):
    now=q.get()
    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''

finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       '''

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])
### BUGGY CODE ###

H, N = map(int, input().split())
ATK = []
dmg_max = []
mp = 0
for i in range(N):	
  ATK.append(list(map(int, input().split())))

while True:
  dmg_max.append(max([dmg_max[mp-ATK[i][1]] + ATK[i][0] for i in range(N) if mp - ATK[i][1] >= 0] + [0]))
  if dmg_max[-1] >= H:
    break
  mp += 1
  #print(dmg_max)

print(mp)


### FIXED CODE ###

H, N = map(int, input().split())
ATK = []

for i in range(N):	
  ATK.append(list(map(int, input().split())))
mp_min = [0]
for hp in range(1, H+1):
  mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

 # print(mp_min)

print(mp_min[-1])
### BUGGY CODE ###

import sys
from pprint import pprint

def solve(n, k, p):
    E = {}
    p_map = {}
    for i, p_i in enumerate(p):
        E[p_i] = (1.0 + p_i)/2
        p_map[i] = p_i
    # pprint(E)
    
    ans = 0
    for i in range(n - k + 1):
        ans = max(ans, sum([E[p_map[i+j]] for j in range(k)]))
    print(ans)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    p = list(map(int, sys.stdin.readline().strip().split(" ")))
    solve(n, k, p)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, k, p):
    acum_E = [0]
    sum_E = 0
    for i, p_i in enumerate(p):
        sum_E += (1.0 + p_i)/2 
        acum_E.append(sum_E)
    # pprint(acum_E)
    
    ans = 0
    for i in range(n - k + 1):
        # print(i+k, i)
        ans = max(ans, acum_E[i + k] - acum_E[i])
    print(ans)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    p = list(map(int, sys.stdin.readline().strip().split(" ")))
    solve(n, k, p)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1 for _ in range(size)]
        self.__size = [1 for _ in range(size)]

    def find(self, v: int) -> int:
        if self.__root[v] == -1:
            return v
        return self.find(self.__root[v])

    def size(self, v: int) -> int:
        root = self.find(v)
        return self.__size[root]

    def unite(self, u: int, v: int):
        ur, vr = self.find(u), self.find(v)
        if ur > vr:
            ur, vr = vr, ur

        self.__size[ur] += self.__size[vr]
        self.__root[vr] = ur

    def connected(self, u: int, v: int):
        return self.find(u) == self.find(v)

    def print(self):
        print('-' * 5 + ' root ' + '-' * 5)
        print(self.__root)
        print('-' * 5 + ' size ' + '-' * 5)
        print(self.__size)


def decayed_bridges(N: int, M: int, edges: list) -> list:
    ret = [N*(N-1)//2]
    uf = UnionFind(N+1)

    for u, v in reversed(edges):
        ret = [ret[0]] + ret[:]

        if not uf.connected(u, v):
            n1, n2 = uf.size(u), uf.size(v)
            ret[0] -= n1 * n2
            uf.unite(u, v)

    return ret[1:]


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    edges = []
    for _ in range(M):
        a, b = [int(s) for s in input().split()]
        edges.append((a, b))

    answers = decayed_bridges(N, M, edges)

    for a in answers:
        print(a)


### FIXED CODE ###

class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1 for _ in range(size)]

    def find(self, v: int) -> int:
        if self.__root[v] < 0:
            return v
        self.__root[v] = self.find(self.__root[v])
        return self.__root[v]

    def size(self, v: int) -> int:
        r = self.find(v)
        return -self.__root[r]

    def unite(self, u: int, v: int):
        ur, vr = self.find(u), self.find(v)
        if ur == vr:
            return

        if self.size(ur) < self.size(vr):
            ur, vr = vr, ur

        self.__root[ur] += self.__root[vr]
        self.__root[vr] = ur

    def connected(self, u: int, v: int):
        return self.find(u) == self.find(v)


def decayed_bridges(N: int, M: int, edges: list) -> list:
    ret = [0 for _ in range(M)]
    uf = UnionFind(N)

    current = N*(N-1)//2
    for m in range(M-1, -1, -1):
        ret[m] = current

        u, v = edges[m]
        u, v = u-1, v-1

        if not uf.connected(u, v):
            n1, n2 = uf.size(u), uf.size(v)
            current -= n1 * n2
            uf.unite(u, v)

    return ret


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    edges = []
    for _ in range(M):
        a, b = [int(s) for s in input().split()]
        edges.append((a, b))

    answers = decayed_bridges(N, M, edges)

    for a in answers:
        print(a)
### BUGGY CODE ###

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

dp = [float("inf")]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h + 1):
        if j < a[i]:
            dp[j] = min(dp[j], b[i])
        else:
            dp[j] = min(dp[j], dp[j-a[i]]+b[i])

print(dp[h])

### FIXED CODE ###

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

dp = [float("inf")]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h + 1):
        if j < a[i]:
            dp[j] = min(dp[j], b[i])
        else:
            dp[j] = min(dp[j], dp[j-a[i]]+b[i])

print(dp[h])
### BUGGY CODE ###

def solve():
  N, K = map(int, input().split())
  h = list(map(int, input().split()))
  
  INF = 10**9
  dp = [INF] * N
  dp[0] = 0
  dp[1] = abs(h[1] - h[0])
  
  for i in range(2, N):
    for j in range(1, K + 1):
      if i - j >= 0:
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
  print(dp[N - 1])

if __name__ == "__main__":
  solve()

### FIXED CODE ###

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

dp = [0] * N
for i, hi in enumerate(h):
  if i > 0:
    x = max(0, i - K)
    dp[i] = min([dpj + abs(hi - hj) for hj, dpj in zip(h[x:i], dp[x:i])])
print(dp[N - 1])
### BUGGY CODE ###

K,S=map(int,input().split())
cnt=0
K+=1
for i in range(K):
  for j in range(K):
    for k in range(K):
      if i+j+k==S:
        cnt+=1
print(cnt)

### FIXED CODE ###

K,S=map(int,input().split())
cnt=0

for i in range(K+1):
  for j in range(K+1):
    k=S-(i+j)
    if (k>=0) and (k<=K):
      cnt+=1
print(cnt)
### BUGGY CODE ###

s = list(str(input()))

sum = 0
i = 0
while True:
    if s[i] == 'B' and s[i+1] == 'W':
        s[i] = 'W'
        s[i+1] = 'B'
        sum += 1
        if i > 0:
            i = i - 1
        else:
            i += 1
    else:
        i += 1
    
    if i >= len(s) - 1:
        break

print(sum)


### FIXED CODE ###

s = list(str(input()))

sum = 0
bcount = 0
for i in range(len(s)):
    if s[i] == 'B' :
        bcount += 1
    else :
        sum += bcount

print(sum)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

    return wf #wf[i][j]に頂点i, j間の最短距離を格納

##############################

n = int(input())
d = [list(map(int,input().split())) for _ in range(n)]

if d != warshall_floyd(d):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i+1,n):
            if i == j: continue
            ret += d[i][j]
            for mid in range(n):
                if mid in (i, j): continue
                if d[i][mid] + d[mid][j] == d[i][j]:
                    ret -= d[i][j]
                    break
    print(ret)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

    return wf #wf[i][j]に頂点i, j間の最短距離を格納

##############################

n = int(input())
d = [list(map(int,input().split())) for _ in range(n)]

if d != warshall_floyd(d):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i+1,n):
            if i == j: continue
            ret += d[i][j]
            for mid in range(n):
                if mid in (i, j): continue
                if d[i][mid] + d[mid][j] == d[i][j]:
                    ret -= d[i][j]
                    break
    print(ret)
### BUGGY CODE ###

n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

### FIXED CODE ###

n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))