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

N = int(input())

c_list = [s for s in input()]
cr = list(reversed(c_list))
back = N - 1


def check(forward):
    global back
    for i in range(back, -1, -1):
        if i < forward:
            return -1
        if c_list[i] == "R":
            back -= 1
            return i
    return -1


count = 0
for i, c in enumerate(c_list):
    if c_list[i] == "W":
        temp = check(i + 1)
        if temp != -1:
            c_list[i] = "R"
            c_list[temp] = "W"
            count += 1
        else:
            break
print(count)

### FIXED CODE ###

N = int(input())

c_list = [s for s in input()]
back = N - 1


def check(forward):
    global back
    for i in range(back, -1, -1):
        if i < forward:
            return -1
        if c_list[i] == "R":
            back = i - 1
            return i
    return -1


count = 0
for i, c in enumerate(c_list):
    if c_list[i] == "W":
        temp = check(i + 1)
        if temp != -1:
            c_list[i] = "R"
            c_list[temp] = "W"
            count += 1
        else:
            break
print(count)
### BUGGY CODE ###

def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import collections

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

c = collections.Counter(lis)
dic = {}

for i in range(n):
    if lis[i] in dic.keys():
        continue
    else:
        if c[lis[i]] < 2:
            dic[lis[i]] = 0
        else:
            dic[lis[i]] = cmb(c[lis[i]], 2)


for i in range(n):
    ans = sum(list(dic.values()))
    ans -= dic[lis[i]]
    if c[lis[i]] <= 2:
        ans += 0
    else:
        ans += cmb(c[lis[i]]-1, 2)
    
    print(ans)

### FIXED CODE ###


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

ban = [0] * n

tmp = 0
for i in lis:
    ban[i-1] += 1

for i in ban:
    tmp += i*(i-1)//2
    
for i in lis:
    print(tmp+(1-ban[i-1]))
### BUGGY CODE ###

import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
ans=0
for a in A:
  b=bisect.bisect_left(B,a+1)
  for i in range(n-b):
    ans+=n-bisect.bisect_left(C,B[b+i]+1)
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
print(sum(bisect.bisect_left(A,b)*(n-bisect.bisect_right(C,b)) for b in B))
### BUGGY CODE ###

input()
strs = input().split(' ')
nums = [int(i) for i in strs]

ct = 0
b_flag = False
while(1):
  for num in nums:
    if num % 2 == 0:
      continue
    else:
      b_flag = True
      break
  if b_flag:
    break
  ct += 1
print(ct)
  

### FIXED CODE ###

input()
strs = input().split(' ')
nums = [int(i) for i in strs]

ct = 0
b_flag = False
while(1):
  for i, num in enumerate(nums):
    if num % 2 == 0:
      nums[i] = num/2
      continue
    else:
      b_flag = True
      break  
  if b_flag:
    break
  ct += 1
print(ct)
### BUGGY CODE ###

int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print(max(dp_memo))
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

### FIXED CODE ###

H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)
### BUGGY CODE ###

L, R = map(int, input().split())
ans = 2019
for i in range(L, R+1):
    for j in range(i+1, R+1):
        ans = min(ans, i*j%2019)
        if ans == 0:
            break
print(ans)

### FIXED CODE ###

import sys
l,r = map(int,input().split())
a=[]

for i in range(l,r):
	for j in range(i+1,r+1):
		a.append((i*j)%2019)

		if (i*j)%2019 == 0:
			print(0)
			sys.exit()
print(min(a))
### BUGGY CODE ###

n = int(input())
for i in range(1, n+1):
    ans = 0
    for x in range(1, int(i**0.5)+1):
        for y in range(1,int(i**0.5)+1):
            if -2*x*y - (3 * x**2) - (3 * y**2) + 4*i >= 0:
                if (-(y + x) + (-2*x*y - (3 * x**2) - (3 * y**2) + 4*i)**0.5) % 2 == 0 and (-(y + x) + (-2*x*y - (3 * x**2) - (3 * y**2) + 4*i)**0.5) / 2 >= 1:
                    ans += 1
            else:
                break
    print(ans)

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(n + 1)]
for x in range(1,int(pow(n, 0.5)+1)):
    for y in range(1,int(pow(n, 0.5)+1)):
        for z in range(1,int(pow(n, 0.5)+1)):
            if x**2 + y**2+z**2 +x*y + x*z + y*z <= n:
                ans [x**2 + y**2+z**2 +x*y + x*z + y*z] += 1
for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

from operator import itemgetter

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    BC.append(tmp)
A.sort(reverse=True)
BC.sort(key=itemgetter(1),reverse=True)

l = 0
r = N-1
flg = False
for k in range(M):
    # l tansaku
    for p in range(N):
        if BC[k][1] > A[p]:
            l = p
            break
        elif p == N-1:
            flg = True
    #break
    if flg or r < l: break
    tmpC = BC[k][1]
    #chikan
    for o in range(BC[k][0]):
        if r < l or r == -1:
            flg = True
            break
        A[r] = tmpC
        r -= 1

print(sum(A))

### FIXED CODE ###

from operator import itemgetter

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    BC.append(tmp)
A.sort(reverse=True)
BC.sort(key=itemgetter(1),reverse=True)

l = 0
r = N-1
flg = False
for k in range(M):
    # l tansaku
    for p in range(l,N):
        if BC[k][1] > A[p]:
            l = p
            break
        elif p == N-1:
            flg = True
    #break
    if flg or r < l: break
    tmpC = BC[k][1]
    #chikan
    for o in range(BC[k][0]):
        if r < l or r == -1:
            flg = True
            break
        A[r] = tmpC
        r -= 1

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

import sys
input = sys.stdin.readline

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

seg = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for i, L in enumerate(Ls):
            P = []
            for k, v in L:
                P.append((B[k], v))
            P.sort(reverse=True)
            if i == 0:
                maxp = P[0][1]
            elif P[0][1] >= maxp:
                maxp = P[0][1]
            else:
                continue
            Q = []
            for p, v in P:
                Q.extend([p]*v)
            num = int(''.join([str(q) for q in Q]))
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

NUM = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10**14

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for a in A:
        c = NUM[a]
        if i + c <= N:
            dp[i+c] = max(dp[i+c], dp[i]+1)

D = dp[N]
ind = N
ans = ''
for _ in range(D):
    for a in A:
        c = NUM[a]
        if ind - c < 0: continue
        if dp[ind] == dp[ind-c] + 1:
            ind -= c
            ans += str(a)
            break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N, M , K = [int(x) for x in input().split()]
AB = []
G_F = [deque([]) for _ in range(N)]
G_B = [deque([]) for _ in range(N)]
G_F_s = [set() for _ in range(N)]
G_B_s = [set() for _ in range(N)]
for _ in range(M):
    AB = [int(x) for x in input().split()]
    G_F[AB[0] - 1].append(AB[1] - 1)
    G_F[AB[1] - 1].append(AB[0] - 1)
    G_F_s[AB[0] - 1].add(AB[1] - 1)
    G_F_s[AB[1] - 1].add(AB[0] - 1)

CD = []
for _ in range(K):
    CD = [int(x) for x in input().split()]

    G_B[CD[0] - 1].append(CD[1] - 1)
    G_B[CD[1] - 1].append(CD[0] - 1)
    G_B_s[CD[0] - 1].add(CD[1] - 1)
    G_B_s[CD[1] - 1].add(CD[0] - 1)

ans = 0
from collections import deque
G_F = deque(G_F)
G_B = deque(G_B)

# グラフの作成(無向グラフでは#を消す)

time = 0
arrive_time = [-1] * (N) # 到着時刻

# 深さ優先探索
def dfs(v, graph):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time
import copy
ans = [0] * N
for i in range(N - 1):
    arrive_time = [-1] * N
    graph = copy.deepcopy(G_F)
    arrive_time = dfs(i, graph)
    for j in range(i + 1, N):
        if j in G_B_s[i] or j in G_F_s[i]:
            continue
        if arrive_time[j] > 0:
            ans[i] += 1
            ans[j] += 1

print(*ans)




### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [[] * n for _ in range(n)]

 
#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    unite(a - 1, b - 1)
    ab[a - 1].add(b - 1)
    ab[b - 1].add(a - 1)

for i in range(k):
    c, d = [int(x) for x in input().split()]
    if same(c - 1, d - 1):
        cd[c - 1].append(d - 1)
        cd[d - 1].append(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

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

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
p = l()

for i in range(n):
    p[i] = (p[i]+1)/2

for i in range(n-k+1):
    a = p[i:i+k]
    ans = max(ans,sum(a))

print(ans)


### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
p = l()
x = list(itertools.accumulate(p))

if n==1:
    print((p[0]+1)/2)
    sys.exit()

if n==k:
    print((x[-1]+k)/2)
    sys.exit()

for i in range(1,n-k+1):
    ans = max(ans,x[i+k-1]-x[i-1])

print((ans+k)/2)
### BUGGY CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if M % i == 0:
        ans = i
print(ans)


### FIXED CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if i * i > M:
        break
    if M % i == 0:
        j = M // i
        if j <= V:
            ans = max(ans, j)
        else:
            ans = max(ans, i)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])


### FIXED CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])
### BUGGY CODE ###

s=str(input())
temps=list(s)
temp=0
for i in range(0,len(temps)):
  if temps[i]=="W":
    temps[i]=1
  if temps[i]=="B":
    temps[i]=0
for i in range(0,len(temps)):
  if temps[i]==0:
    temp=temp+sum(temps[i+1:len(s)])
print(temp)

### FIXED CODE ###

s=str(input())
s=list(s)
count=0
temp=0
for i in range(len(s)):
  if s[i]=="W":
    temp=temp+i-count
    count=count+1
print(temp)
### BUGGY CODE ###

from functools import reduce
from math import gcd
k=int(input())
ans=0
for i in range(k):
	for j in range(k):
		for p in range(k):
			ans+=reduce(gcd, [i+1,j+1,p+1])
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
	return reduce(math.gcd, numbers)
k=int(input())
ans=0
for i in range(k):
	for j in range(k):
		for p in range(k):
			ans+=gcd(i+1,j+1,p+1)
print(ans)
### BUGGY CODE ###

n=int(input())
xy=[]
for i in range(n):
  tmp=list(map(int,input().split()))
  xy.append(tmp)
ans=0
for i in range(n):
  for j in range(i,n):
    tmp=abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1])
    ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

n=int(input())
z=[]
w=[]
for i in range(n):
  x,y=map(int,input().split())
  z.append(x+y)
  w.append(x-y)
ans=max(max(z)-min(z), max(w)-min(w))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))

l,r,u,d = [[[0 for w in range(W)] for h in range(H)] for _ in range(4)]


for h in range(H):
  for w in range(W):
    s = S[h][w]
    l[h][w] = (l[h][w-1]+1)*S[h][w]
    r[h][-w-1] = (r[h][-w]+1)*S[h][-w-1]
    u[h][w] = (u[h-1][w]+1)*S[h][w]
    d[-h-1][w] = (d[-h][w]+1)*S[-h-1][w]
  
ans = 0
for h in range(H):
  for w in range(W):
    tmp =(l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)*S[h][w]
    ans = max(ans, tmp)
    
print(ans)
    




### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

N, *A = map(int, open(0).read().split())

A.sort()

ans = 0
for i in range(N):
    count = 1
    for j in range(i+1, N):
        if A[j] <= A[i] + 2:
            count += 1
        else:
            break
    ans = max(ans, count)

print(ans)

### FIXED CODE ###

import sys
import collections

N, *A = map(int, open(0).read().split())

B = collections.Counter(A).most_common()
B.sort(key=lambda x: x[0])

ans = 0
for i in range(len(B)):
    count = B[i][1]
    if i+1 < len(B) and B[i+1][0] == B[i][0]+1:
        count += B[i+1][1]
        if i+2 < len(B) and B[i+2][0] == B[i][0]+2:
            count += B[i+2][1]
    ans = max(ans, count)
print(ans)
### BUGGY CODE ###

"""
この解答に自分用にコメントつけただけ
https://atcoder.jp/contests/abc135/submissions/6585300
"""

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
    # dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
    MOD = 10**9 + 7

    dp[0][0] = 1 # 何もなしのとき０とする

    """
    たとえば５６７８という数字について考えるとき
    5：s[1][5] = 1で他のjが０
    56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
    先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
    """

    for i in range(1, len(S)+1):
        if S[i-1] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
        else:
            for k in range(13):
                dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

    print(dp[-1][5] % MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

"""
この解答に自分用にコメントつけただけ
https://atcoder.jp/contests/abc135/submissions/6585300
"""

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
    # dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
    MOD = 10**9 + 7

    dp[0][0] = 1 # 何もなしのとき０とする

    """
    たとえば５６７８という数字について考えるとき
    5：s[1][5] = 1で他のjが０
    56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
    先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
    """

    for i in range(1, len(S)+1):
        if S[i-1] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
        else:
            for k in range(13):
                dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

    print(dp[-1][5] % MOD)

if __name__ == "__main__":
    main()