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

from collections import deque
X = str(input())
X = X.replace("ST","")
lx = len(X)
st = deque([])

for i in range(lx):
  if X[i] == "S":
    st.append("S")
  else:
    if "S" in st:
      st.pop()
    else:
      st.appendleft("T")
   
print(len(st))

### FIXED CODE ###

X = str(input())
X = X.replace("ST","")
lx = len(X)
s_count = 0
t_count = 0
for i in range(lx):
  if X[i] == "S":
    s_count += 1
  else:
    if s_count:
      s_count -= 1
    else:
      t_count += 1
   
print(s_count + t_count)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    row = S[h]
    for w in range(W):
        if w > 0 and row[w] != '#' and count_matw[h][w-1] != 0:
            count_matw[h][w] = count_matw[h][w-1]
            continue
        if '#' in row[w:]:
            obs_i = row[w:].index('#')
            count_matw[h][w] = obs_i
        else:
            count_matw[h][w] = W-w
for w in range(W):
    col = [row[w] for row in S]
    for h in range(H):
        if h > 0 and col[h] != '#' and count_math[h-1][w] != 0:
            count_math[h][w] = count_math[h-1][w]
            continue
        if '#' in col[h:]:
            obs_i = col[h:].index('#')
            count_math[h][w] = obs_i
        else:
            count_math[h][w] = H-h
ans = 1
for h in range(H):
    for w in range(W):
        ans = max(ans, count_math[h][w] + count_matw[h][w])
# print(count_math)
# print(count_matw)
print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    count = 0
    for w in range(W):
        if '#' == S[h][w]:
            count = 0
        else:
            count += 1
        count_matw[h][w] = count
    for w in range(W-1, 0, -1):
        if count_matw[h][w-1] == 0:
            continue
        count_matw[h][w-1] = max(count_matw[h][w], count_matw[h][w-1])

for w in range(W):
    count = 0
    for h in range(H):
        if '#' == S[h][w]:
            count = 0
        else:
            count += 1
        count_math[h][w] = count
    for h in range(H-1, 0, -1):
        if count_math[h-1][w] == 0:
            continue
        count_math[h-1][w] = max(count_math[h][w], count_math[h-1][w])
ans = 1
# for h in range(H):
#     for w in range(W):
#         ans = max(ans, count_math[h][w] + count_matw[h][w])
ans = max([count_math[h][w] + count_matw[h][w] for h in range(H) for w in range(W)])
# print(count_math)
# print(count_matw)
print(ans-1)
### BUGGY CODE ###

n, t = map(int, input().split(" "))
list_a = list(map(int, input().split(" ")))
list_profit = []
for i, a in enumerate(list_a[:-1]):
  max_price = max(list_a[(i+1):])
  if a < max_price:
    list_profit.append(max_price - a)
  else:
    list_profit.append(0)
max_profit = max(list_profit)
print(list_profit.count(max_profit))

### FIXED CODE ###

n, t = map(int, input().split(" "))
list_a = list(map(int, input().split(" ")))
list_profit = []
min_price = list_a[0]
for a in list_a:
  if min_price < a:
    list_profit.append(a - min_price)
  else:
    list_profit.append(0)
    min_price = a
max_profit = max(list_profit)
print(list_profit.count(max_profit))
### BUGGY CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    res = []
    
    for i in range(len(n)):
        a = int(n[i:])
        res.append(a%2019)
    res.append(0)
    c = Counter(res)
    ans = 0
    for i in c.values():
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 1
    c = 0
    for i in range(len(n)):
        a = int(n[i])
        c += a*b
        c %= 2019
        res[c] += 1
        b = b*10%2019
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

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

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

while N>=K:
  N = N - K

while N!=0:
  if N>=abs(N-K):
    N = N-K
    if N<0:
      N = N * -1
  elif N==0:
    break
  else:
    break            
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
if N>=K:
  N = N%K

while N!=0:
  if N>=abs(N-K):
    N = abs(N-K)
  elif N==0:
    break  
  else:
    break
print(N)
### BUGGY CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
n_list=  [['' for i in range(a)] for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    n_list[i][0]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[0][i]=t[0]


for i in range(1,b) :
  for j in range(1,a) :
    if len(n_list[i-1][j])>len(n_list[i][j]) :
      n_list[i][j]=n_list[i-1][j]
    if len(n_list[i][j-1])>len(n_list[i][j]) :
      n_list[i][j]=n_list[i][j-1]
    if t[i]==s[j] and len(n_list[i-1][j-1])+1>len(n_list[i][j])  :
      n_list[i][j] = n_list[i-1][j - 1]+t[i]

print(n_list[-1][-1])

### FIXED CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.copy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :

    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

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

def main():
    N = int(input())
    S = [sorted(input()) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i]==S[j]:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N = int(input())

    S = []
    d = {}
    ans = 0
    for _ in range(N):
        t = input()
        t = "".join(sorted(t))
        if t in d:
            ans += d[t]
            d[t] += 1
        else:
            d[t] = 1

    print(ans)

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

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
p_list_copy = p_list.copy()

scope_index = -1
max_sum = 0
for p_i in range(len(p_list_copy)):
    now_sum = 0
    for i in range(k):
        if len(p_list_copy) < k:
            break
        now_sum += p_list_copy[i]

    if max_sum < now_sum:
        max_sum = now_sum
        scope_index = p_i
    p_list_copy.pop(0)

max_scope_list = []
for i in range(k):
    max_scope_list.append(p_list[scope_index + i])

ex = 0
for scope in max_scope_list:
    for num in range(1, scope+1):
        ex += num*1/scope
print(ex)


### FIXED CODE ###

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

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input())
    sl = list(input())
    sl.pop()

    q = int(input())
    kl = list(map(int,input().split()))

    for k in kl:
        # i文字目までのdとmとdmの数

        d = m = dm = ans = 0
        for i in range(n):
            if i - k >= 0:
                if sl[i-k] == "D":
                    d -= 1
                    dm -= m
                if sl[i-k] == "M":
                    m -= 1
            if sl[i] == "D":
                d += 1
            if sl[i] == "M":
                m += 1
                dm += d
            if sl[i] == "C":
                ans += dm

        print(ans)

if __name__ == "__main__":
    main()







### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
Q = int(input())

mode = 1
for i in range(Q):
  query = input()
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        #S = C+S # add to last
        S = "".join([C,S])
      else:
        #S = S+C # add to beginning
        S = "".join([S,C])
    else:
      if mode==1:
        #S = S+C # add to beginning
        S = "".join([S,C])
      else:
        #S = C+S # add to last
        S = "".join([C,S])

if mode==-1:
  S = S[::-1]

print(S)


### FIXED CODE ###

S = input()
Q = int(input())

add_to_last = []
add_to_beginning = []

queries = [input() for _ in range(Q)]

mode = 1
for i in range(Q):
  query = queries[i]
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        add_to_beginning.append(C)
      else:
        add_to_last.append(C)
    else:
      if mode==1:
        add_to_last.append(C)
      else:
        add_to_beginning.append(C)   

if mode==1:
  add_to_beginning.reverse()
  print("".join(add_to_beginning), end="")
  print(S, end="")
  print("".join(add_to_last))
else:
  add_to_last.reverse()
  print("".join(add_to_last), end="")
  print(S[::-1], end="")
  print("".join(add_to_beginning))
### BUGGY CODE ###

MOD = 10**9+7
k = input()
d = int(input())
n = len(k)
dp = [[0] * 2 for _ in range(d)]
# dp[sum][smaller_already] - the number of ways to choose digits so far
# such that the sum of digits modulo D is 'sum' and 'smaller_already'
# says whether we already chosen some digit smaller than in K
dp[0][0] = 1
for i in range(n):
    new_dp = [[0] * 2 for _ in range(d)]
    for sums in range(d):
        for sm_already in (False, True):
            for digit in range(10):
                if digit > int(k[i]) and not sm_already:
                    break
                new_dp[(sums + digit) % d][sm_already or (digit < int(k[i]))] += dp[sums][sm_already]
    dp = new_dp
res = (dp[0][False] + dp[0][True] - 1) % MOD
print(res)

### FIXED CODE ###

K = int(input())
D = int(input())
mod = 10**9 + 7

dp = [[[0] * D for _ in range(2)] for _ in range(len(str(K))+1)]
dp[0][0][0] = 1

for i in range(len(str(K))):
    N = int(str(K)[i])
    for j in range(2):
        for k in range(D):
            for n in range((9 if j == 1 else N) + 1):
                dp[i+1][j or n < N][(k+n%D)%D] += dp[i][j][k]%mod

print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)
### BUGGY CODE ###

from collections import Counter
N = int(input())
val2ind = Counter(list(map(int, input().split())))
Q = int(input())

for _ in range(Q):
    B, C = list(map(int, input().split()))
    if B in val2ind:
        cand = val2ind[B]
        del val2ind[B]
        if C not in val2ind:
            val2ind[C] = cand
        else:
            val2ind[C] += cand
    print(sum([key*val2ind[key] for key in val2ind]))

### FIXED CODE ###

from collections import Counter
N = int(input())
val2ind = Counter(list(map(int, input().split())))
ans = sum([key*val2ind[key] for key in val2ind])
Q = int(input())

for _ in range(Q):
    B, C = list(map(int, input().split()))
    if B in val2ind:
        cand = val2ind[B]
        del val2ind[B]
        if C not in val2ind:
            val2ind[C] = cand
        else:
            val2ind[C] += cand
        ans = ans+(C-B)*cand
    print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
  l, r = map(int, input().split())
  sub_s = s[l-1:r]
  print(sub_s.count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC109C
import sys

s = input()
t = input()

#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#n=hoge[0]
#x=hoge[1]

for i in range(0,len(s)-1):
	for j in range(i+1,len(s)):
		if(s[i]==s[j]):
			if(t[i]!=t[j]):
				print("No")
				sys.exit()
		else:
			if(t[i]==t[j]):
				print("No")
				sys.exit()
print("Yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC110C
import sys

s = input()
t = input()

#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#n=hoge[0]
#x=hoge[1]

checktable=[]
checktable2=[]
for i in range(0,26):
	checktable.append(0)
	checktable2.append(0)

for i in range(0,len(s)):
	index=ord(s[i])-ord("a")
	if(checktable[index]==0):
		checktable[index]=ord(t[i])-ord("a")
	else:
		if(checktable[index]!=ord(t[i])-ord("a")):
			print("No")
			sys.exit()
for i in range(0,len(s)):
	index=ord(t[i])-ord("a")
	if(checktable2[index]==0):
		checktable2[index]=ord(s[i])-ord("a")
	else:
		if(checktable2[index]!=ord(s[i])-ord("a")):
			print("No")
			sys.exit()
print("Yes")
### BUGGY CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort()
q.sort()
p.reverse()
q.reverse()

a=p[:]
a.extend(q)
a.extend(r)
a.sort()
a.reverse()
b=q[:]
b.extend(r)
b.sort()
b.reverse()
c=p[:]
c.extend(r)
c.sort()
c.reverse()
red=0
green=0
sum=0
sum1=0
sum2=0
d=0
for i in range(X+Y):
  if(a[i] in p):
    red+=1
  elif(a[i] in q):
    green+=1
  d+=a[i]
 
  if(i<X):
      sum1+=p[i]
      sum2+=c[i]
  if(i<Y):
      sum1+=b[i]
      sum2+=q[i]
    
if(red<=X and green<=Y):
  print(d)
elif(red>X):
  print(sum1)
elif(green>Y):
  print(sum2)

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort()
q.sort()
p.reverse()
q.reverse()
p=p[:X]
q=q[:Y]
 
a=p[:]
a.extend(q)
a.extend(r)
a.sort()
a.reverse()
sum=0
for i in range(X+Y):
  sum+=a[i]
print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#S = list(input())
	#L,R = map(int, input().split(" "))
	#L = list(map(int, input().split(" ")))

	A = input().split()
	A = [int(s) for s in A]

	ans = [0 for _ in range(N)]
	
	ed = min(A[0]*2, A[-1]*2)
	for i in range(0, ed+1, 2):
		fin = True
		for j in range(N):
			if j == 0:
				ans[j] = i
				continue
			tmp = (A[j-1] - (ans[j-1] / 2))*2

			if tmp < 0 or tmp % 2 == 1:
				fin = False
				break
			else :
				ans[j] = int(tmp)
		
		if fin == False:
			pass
		else:
			if (ans[-1] / 2) + (ans[0] / 2) == A[-1]:
				#print("sss")
				break

	ans = [str(a) for a in ans]
	print(' '.join(ans))




if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	A = input().split(" ")
	A = [int(s) for s in A]
	
	tmp = 0
	for i, val in enumerate(A):
		if i == 0:
			tmp += 2*val
			continue
		if i % 2 == 1:
			tmp -= 2*val
		else:
			tmp += 2*val
	
	x = tmp / 2
	
	ans = []
	ans.append(int(x))
	for i, val in enumerate(A):
		tmp = (val - (ans[i]/2)) * 2
		ans.append(int(tmp))
	
	ans = ans[:-1]
	ans = [str(s) for s in ans]
	print(" ".join(ans))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

K,S = map(int,input().split())
count = 0
for l in range(K+1):
    for m in range(K+1):
        for n in range(K+1):
            s = l+m+n
            if s==S:
                count = count+1
print(count)

### FIXED CODE ###

K,S=input().split()
K=int(K)
S=int(S)
A=0
for x in range(0,K+1):
    for y in range(0,K+1):
        z=S-x-y
        if 0<=z<=K:
            A=A+1
print(A)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
ans = 0
tmp = 0
while(i < n - 1):
    j = 1
    while(i + j < n):
        tmp += a[i + j]
        j += 1
    ans += (a[i] * tmp) % (10**9 + 7)
    i+=1
    tmp = 0
ans = ans % (10**9 + 7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
tmp = 0
tmpura = 0
while(i < n):
    tmp += a[i]
    i+=1
tmp=tmp **2
i = 0
while (i < n):
    tmpura += a[i]**2
    i+=1
tmpura=tmpura
ans = ((tmp - tmpura)//2)%(10**9+7)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

if 'R' != 'G' != 'R' != 'R':
    print('yes')


count = 0
for i in range(0, N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if j - i != k - j:
                if S[i] != S[j] != S[k] != S[i]:
                    count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = list(input())

# RGBとなる組み合わせの数を求める
sum_collection = S.count('R') * S.count('G') * S.count('B')

# RGBとなる組み合わせの数から、 j - i == k - jとなる組の数を減らす
for i in range(N):
    for j in range(i, N):
        # j - i == k - j　となる組を見つける
        k = j + (j - i)
        if k >= N:
            break
        # すべて違ったら　(R G Bの組み合わせであったら)
        if S[i] != S[j] != S[k] != S[i]:
            sum_collection -= 1

print(sum_collection)
### BUGGY CODE ###

def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0 for _ in range(W)] for __ in range(g)]
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(len(now)):
                now[n] = now[n] + v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0 for _ in range(W)] for __ in range(g)]
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(len(now)):
                now[n] = now[n] + v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

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

S = input()
dp = [[0]*13 for _ in range(len(S))]
if S[0]=="?":
  dp[0] = [1]*10+[0]*3
else:
  dp[0][int(S[0])] = 1
mod = 10**9+7
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])
    
    

### FIXED CODE ###

S = input()
dp = [[0]*13 for _ in range(len(S))]
if S[0]=="?":
  dp[0] = [1]*10+[0]*3
else:
  dp[0][int(S[0])] = 1
mod = 10**9+7
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])