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

#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
ans = ans%1000000007
print(int(ans))

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N,K = map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))

    A.sort()
    F.sort(reverse=True)

    B=[]
    for i in range(N):
        B.append((A[i]*F[i],F[i]))

    B.sort()
    for _ in range(K):
        if not len(B) > 0:
            break
        b,f = B.pop()
        front = (b-f,f)

        if b-f > 0:
            bisect.insort(B,front)

    print(max(B)[0] if len(B) > 0 else 0)
    # print(B)



if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N,K = map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))

    A.sort()
    F.sort(reverse=True)

    def c(s): # sに対して単調減少
        sum_x = 0
        for i in range(N):
            a,f=A[i],F[i]
            tp = s//f
            if not a <= tp:
                sum_x += a-tp

        return sum_x <= K

    l=-1
    r=10**20
    while r-l>1:
        mid = (l+r)//2
        if c(mid):
            r = mid
        else:
            l = mid

    print(r)

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

# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる
def main():
    from collections import deque
    N = int(input())
    graph = {i:[] for i in range(N)}
    AB = [[0] * 2 for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
        AB[i][0], AB[i][1] = a, b
        if i == 0:
            start = a

    K = 0
    for some in graph.values():
        K = max(len(some), K)

    # BFSのためのデータ構造
    que = deque()
    dist = [False] * N

    # 初期条件
    que.append(start)
    color_num = {i:{} for i in range(N)}
    dist[start] = True

    # BFS開始
    while que:
        v = que[0]
        que.popleft()
        tmp = 0
        for new_v in graph[v]:
            if dist[new_v]:
                continue
            # 新たな頂点 new_vについて距離情報を更新してキューを追加する
            dist[new_v] = True
            que.append(new_v)
            # 色を塗る
            for k in range(tmp+1, K+1):
                if k in color_num[v].values():
                    continue
                else:
                    color_num[v][new_v] = k
                    color_num[new_v][v] = k
                    tmp = k
                    break
    # 答えの出力
    print(K)
    for i in range(N-1):
        print(color_num[AB[i][0]][AB[i][1]])

if __name__ == "__main__":
    main()

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
### BUGGY CODE ###

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

#print(N)
#print(P)

SUCCESS = N
for i in range(N):
    j = i - 1
    while j >= 0:
        if P[i] > P[j]:
            #print("Fail", i,j)
            SUCCESS -= 1
            break        
        j -= 1

print(SUCCESS)


### FIXED CODE ###

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

#print(N)
#print(P)

SUCCESS = N
pre_max = P[0]
pre_min = P[0]
for i in range(N):
    j = i - 1

    if pre_min < P[i]:
        SUCCESS -= 1
        continue
    else:
        pre_min = P[i]
print(SUCCESS)
### BUGGY CODE ###


import numpy as np
ans=0
D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([-1 for _ in range(26)])
score=np.array([list(map(int,input().split())) for _ in range(D)])

for day in range(D):
    today_point=C*(day-last_day)
    S_today=sum(today_point)
    for k in range(26):
        today_point[k]=score[day][k]-S_today+today_point[k]

    if day<D-2:
        max_score=-1*float("inf")
        for k in range(26):
            nday_point=C*((day+1)-last_day)
            S_nday=sum(nday_point)-C[k]*(day-last_day[k])
            
            for i in range(26):
                if k!=i:
                    nday_point[i]=score[day+1][i]-S_nday+nday_point[i]
                else:
                    nday_point[i]=score[day+1][i]-S_nday+C[i]

                if today_point[k]+nday_point[i]>max_score:
                    max_score=today_point[k]+nday_point[i]
                    idx=k

                nnday_point=C*((day+2)-last_day)
                S_nnday=sum(nnday_point)-C[k]*(day+1-last_day[k])

                for t in range(26):
                    if t!=i:
                        nnday_point[i]=score[day+2][t]-S_nnday+nnday_point[i]
                    else:
                        nnday_point[i]=score[day+2][t]-S_nnday+C[i]

                    if today_point[k]+nday_point[i]+nnday_point[t]>max_score:
                        max_score=today_point[k]+nday_point[i]+nnday_point[t]
                        idx=k
    else:
        idx=np.argmax(today_point)

    last_day[idx]=day
    print(idx+1)


### FIXED CODE ###

import numpy as np
ans=0
D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([0 for _ in range(26)])

for day in range(1,D+1):
    score=np.array(list(map(int,input().split())))
    tmp=C*(last_day-day)
    #今回行うコンテストで得られる
    idx=np.argmax(tmp+score)
    # ans=ans+score[idx]+np.sum(tmp)+abs(tmp[idx])
    last_day[idx]=day
    print(idx+1)
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(lambda x: int(x) - 1, input().split())
gx, gy = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
d = [[INF] * W for _ in range(H)]
d[sx][sy] = 0
q.appendleft((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

ans = d[gx][gy] if d[gx][gy] < INF else -1
print(ans)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    b = [int(s) for s in input().split()]
    c = [int(s) for s in input().split()]
    print(solve(n, a, b, c))

def solve(n, a, b, c):
    d = [c, b, a]
    dp = []
    dp.append([1 for _ in range(n)])
    dp.append([0 for _ in range(n)])
    dp.append([0 for _ in range(n)])

    for i in range(1, 3):
        for j in range(n):
            dp[i][j] = sum(dp[i-1][k] for k in range(n) if d[i-1][k] > d[i][j])

    return sum(dp[2])


def ilen(it):
    c = 0
    for _ in it:
        c += 1
    return c

main()


### FIXED CODE ###

import bisect

def main():
    n = int(input())
    a = sorted([int(s) for s in input().split()])
    b = sorted([int(s) for s in input().split()])
    c = sorted([int(s) for s in input().split()])
    print(solve(n, a, b, c))

def solve(n, a, b, c):
    d = [c, b, a]
    dp = []
    dp.append([n - i for i in range(n)])
    dp.append([0 for _ in range(n)])
    dp.append([0 for _ in range(n)])

    for i in range(1, 3):
        for j in reversed(range(n)):
            k = bisect.bisect(d[i-1], d[i][j])
            if k == n:
                continue

            dp[i][j] = dp[i-1][k]
            if j != n - 1:
                dp[i][j] += dp[i][j+1]

    return dp[2][0]


def ilen(it):
    c = 0
    for _ in it:
        c += 1
    return c

main()
### BUGGY CODE ###

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    f = 0
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w:
            if s[nh][nw] == '.':
                stack_append([nh, nw, cnt])
            else:
                f = 1
    if f:
        for dh, dw in nex:
            nh = curh + dh
            nw = curw + dw
            if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
                stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

import collections
N,K=map(int,input().split())
li=list(map(int,input().split()))
li_count=collections.Counter(li)
not_change=0
S=min(K,len(li_count))
for k in range(S):
    not_change+=li_count.most_common()[k][1]
print(N-not_change)


### FIXED CODE ###

import collections
N,K=map(int,input().split())
li=list(map(int,input().split()))
li_count=collections.Counter(li)
li_count_most=li_count.most_common()[::-1]
change=0
S=max(len(li_count)-K,0)
for s in range(S):
    change+=li_count_most[s][1]
print(change)
### BUGGY CODE ###


def main():
    n = int(input())
    s = input()
    dic = {'R':[],'G':[],'B':[]}
    for i in range(n):
        if s[i]== 'R':
            dic['R'].append(i)
        elif s[i]== 'G':
            dic['G'].append(i)
        else:
            dic['B'].append(i)
    cnt = 0
    for i in dic['R']:
        for j in dic['G']:
            cnt += len(dic['B'])
            if j+j-i in dic['B']:
                cnt -=1
            if abs(j-i)%2==0 and (j+i)//2 in dic['B']:
                cnt -=1
            if i+i-j in dic['B']:
                cnt -=1 
    print(cnt)
     
            
if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n = int(input())
    s = input()
    dic = {'R':[],'G':[],'B':[]}
    for i in range(n):
        if s[i]== 'R':
            dic['R'].append(i)
        elif s[i]== 'G':
            dic['G'].append(i)
        else:
            dic['B'].append(i)
    cnt = len(dic['R'])*len(dic['G'])*len(dic['B'])
    for i in range(1,n//2+1):
        for j in range(n-2*i):
            if s[j]!=s[j+i] and s[j+i] != s[j+i+i] and s[j]!=s[j+i+i]:
                cnt -=1
    print(cnt)
     
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])
"""
for bc in BC:
    bc = [int(i) for i in bc]
"""
#print(BC)
sum = sum(A)
for bc in BC:
    count = 0
    for i in range(0,len(A)):
        if A[i] == bc[0]:
            A[i] = bc[1]
            count += 1
  #  print("A:",A)
    sum += (bc[1]-bc[0])*count
    print (sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])

#print(BC)
yoso_count=[]
for i in range(1,10**5+1):
    yoso_count.append([i,0])

sum = 0
for a in A:
    yoso_count[int(a)-1][1] += 1
    sum += a

#print(yoso_count,sum)

for bc in BC:
    sum += (bc[1] - bc[0])*yoso_count[bc[0]-1][1]
    yoso_count[bc[1]-1][1] += yoso_count[bc[0]-1][1]
    yoso_count[bc[0]-1][1] = 0
    print(sum)
### BUGGY CODE ###

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


tmp=0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if set([S[i],S[j],S[k]])==set(['R','G','B']):
                if k-j!=j-i:
                    tmp+=1
print(tmp)

### FIXED CODE ###

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

R = S.count('R')
G = S.count('G')
B = S.count('B')
tmp = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + (j - i)
        if k >= N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            tmp-=1
print(tmp + R*G*B)
### BUGGY CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i-1] + 1:
        print(-1)
        exit()

result = 0
b = [0 for i in range(n)]
while a != b:
    max_diff = 0
    for i in range(n):
        j = n - i - 1
        if a[j] != b[j]:
            if a[j] > max_diff:
                start = j
                max_diff = a[j]
    for i in range(max_diff):
        b[start - i] = max_diff - i
    result += max_diff

print(result)

### FIXED CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i - 1] + 1:
        print(-1)
        exit()

if n == 1:
    print(0)
    exit()

result = 0

if a[n-1] != 0:
    result += a[n-1]

for i in range(2, n):
    j = n - i
    if a[j] != 0 and a[j] != a[j + 1] - 1:
            result += a[j]

print(result)
### BUGGY CODE ###

import collections
K = int(input())

def lunlun(x):
  X = collections.deque(str(x))
  if len(X)==1:
    return True
  for i in range(len(X)-1):
   if abs(int(X[1]) - int(X.popleft())) >1:
     return False
  return True

i = 0
j = 1
while i<K:
  if lunlun(j):
    i +=1
  j += 1

print(j-1)

### FIXED CODE ###

from collections import deque
import sys
K = int(input())
q = deque([1,2,3,4,5,6,7,8,9])
num = 0
if K<=9:
    print(q[K-1])
    sys.exit()
for i in range(10**5):
    p = q.popleft()
    num += 1
    if num == K:
        print(p)
    if p%10 != 0:
        q.append(p*10+p%10-1)
    q.append(p*10+p%10)
    if p%10 != 9:
        q.append(p*10+p%10+1)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
for i in range(n):
    z = y.copy()
    z.remove(x[i])
    print(z[n//2-1])


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
y1, y2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i] <= y1:
        print(y2)
    else:
        print(y1)
### BUGGY CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

if len(first)==0 or len(second)==0:
	print("IMPOSSIBLE")
else:
	if any(i  in first for i in second)==True:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")


### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

first=set(first)
second=set(second)
if len(first.intersection(second))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

S = list(input())[::-1]
Now = [0 for _ in range(13)]
Next = [0 for _ in range(13)]
for i in range(len(S)):
    Next = [0 for _ in range(13)]
    if i == 0:
        if S[i] != "?":
            Next[int(S[i])] = 1
        else:
            Next = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        if S[i] != "?":
            mod = (int(S[i])*10**i)%13
            for j in range(len(Now)):
                Next[(mod+j)%13] = (Next[(mod+j)%13] + Now[j])%(10**9+7)
        else:
            mod0 = (10**i)%13
            for j in range(10):
                mod = (mod0*j)%13
                for k in range(len(Now)):
                    Next[(mod+k)%13] = (Next[(mod+k)%13] + Now[k])%(10**9+7)
    Now = Next
print(Now[5])

### FIXED CODE ###

S = list(input())[::-1]
Now = [0 for _ in range(13)]
Next = [0 for _ in range(13)]

if S[0] != "?":
    Next[int(S[0])] = 1
else:
    Next = [1,1,1,1,1,1,1,1,1,1,0,0,0]
Now = Next
modq = 1
for i in range(len(S)-1):
    i = i + 1
    Next = [0 for _ in range(13)]
    if S[i] != "?":
        mod = (int(S[i])*10*modq)%13
        for j in range(len(Now)):
            Next[(mod+j)%13] = (Next[(mod+j)%13] + Now[j])%(10**9+7)
        modq = (10*modq)%13
    else:
        modq = (10*modq)%13
        mod = 0
        for j in range(10):
            for k in range(len(Now)):
                Next[(mod+k)%13] = (Next[(mod+k)%13] + Now[k])%(10**9+7)
            mod = (mod + modq)%13
    Now = Next
print(Now[5])