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

from itertools import accumulate, dropwhile
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    r_sum, g_sum, b_sum = [list(accumulate(1 if c == x else 0 for c in S)) for x in 'RGB']
    sums = {'R': r_sum, 'G': g_sum, 'B': b_sum}
    r_idx, g_idx, b_idx = [[i for i, c in enumerate(S) if c == x] for x in 'RGB']
    idxs = {'R': sorted(g_idx + b_idx), 'G': sorted(r_idx + b_idx), 'B': sorted(r_idx + g_idx)}

    ans = 0
    for i in range(N - 2):
        idxs[S[i]] = list(dropwhile(lambda x: i > x, idxs[S[i]]))
        for j in idxs[S[i]]:
            other = 'RGB'.replace(S[i], '').replace(S[j], '')
            ans += sums[other][-1] - sums[other][j]
            k = j + (j - i)
            if k < N and S[k] == other:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate


def main():
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    r_sum, g_sum, b_sum = [list(accumulate(1 if c == x else 0 for c in S)) for x in 'RGB']

    ans = 0
    sums = {'R': r_sum, 'G': g_sum, 'B': b_sum}
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] == S[j]:
                continue
            other = 'RGB'.replace(S[i], '').replace(S[j], '')
            ans += sums[other][-1] - sums[other][j]
            k = j + (j - i)
            if k < N and S[k] == other:
                ans -= 1
    print(ans)


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

#dp[i]:i番目の足場に達した時のコストの最小値
#dp[i] = min(dp[i-k]+abs(h[i]-h[i-k])) (1<=k<=K)
#このままだとO(NK)で間に合わない?

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**18

dp = [inf for i in range(N)]
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
    for j in range(1, min(K+1, i+1)):
        if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
            dp[i] = dp[i-j] + abs(h[i]-h[i-j])

print(dp[N-1])

### FIXED CODE ###

#dp[i]:i番目の足場に達した時のコストの最小値
#dp[i] = min(dp[i-k]+abs(h[i]-h[i-k])) (1<=k<=K)
#このままだとO(NK)で間に合わない?

import numpy as np

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

h = np.array(input().split(), dtype=np.int64)
 
dp = np.zeros(N, dtype=np.int64)

for i in range(1, N):
    L = max(0, i-K)
    dp[i] = np.min(dp[L:i] + np.abs(h[i]-h[L:i]))

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

import numpy as np
from scipy import linalg

N = int(input())
A = [int(i) for i in input().split()]
b = np.array([2*i for i in A])
B = []
for i in range(N):
    l = [0] * N
    l[i % N] = 1
    l[(i+1)%N] = 1
    B.append(l)
A = np.array(B)
LU = linalg.lu_factor(A)
a = map(int, np.linalg.solve(A, b))
print(*a)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
D = [2*a for a in A]
X = [0] * (N+1)
for i in range(N):
    X[i+1] = D[i] - X[i]

X[0] = (X[0] + X[-1])//2

for i in range(N):
    X[i+1] = D[i] - X[i]

print(*X[:-1])
### BUGGY CODE ###

import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]
            wa[i,j]=(wa[i-1,j]+wa[i,j-1])%(10**9+7)
        else:
            wa[i,j]=(wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1]+(10**9+7))%(10**9+7)
output = wa[N,M]
print(int(output))

### FIXED CODE ###

[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = [[0] * (M+1) for i in range(N+1)]
ta[0][0]=1
wa = [[0] * (M+1) for i in range(N+1)]
wa[0][:]=[1]*(M+1)
for i in range(N+1):
    wa[i][0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i][j]=wa[i-1][j-1]
            wa[i][j]=(wa[i-1][j]+wa[i][j-1])%(10**9+7)
        else:
            wa[i][j]=(wa[i-1][j]+wa[i][j-1]-wa[i-1][j-1]+(10**9+7))%(10**9+7)
output = wa[N][M]
print(int(output))
### BUGGY CODE ###

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

for i in range(q):
    print(s[a[i]-1:b[i]].count('AC'))


### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())
d = [list(map(int, input().split())) for i in range(q)]
a = [0,0]
cnt = 0
for i in range(1, n):
    if s[i-1]+s[i] == 'AC':
        cnt += 1
    a.append(cnt)

for i in range(q):
    print(a[d[i][1]]-a[d[i][0]])
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    L = [i+A[i-1] for i in range(1,N+1)]
    R = [i-A[i-1] for i in range(1,N+1)]
    import collections
    Lcnter = collections.Counter(L)
    Rcnter = collections.Counter(R)
    values = set(Lcnter.keys()) & set(Rcnter.keys())
    ans = 0
    for i in values:
        if i in L and i in R:
            ans += Lcnter[i]*Rcnter[i]
    print(ans)
    


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    L = [i+A[i-1] for i in range(1,N+1)]
    R = [i-A[i-1] for i in range(1,N+1)]
    import collections
    Lcnter = collections.Counter(L)
    Rcnter = collections.Counter(R)
    values = set(Lcnter.keys()) & set(Rcnter.keys())
    ans = 0
    for i in values:
        ans += Lcnter[i]*Rcnter[i]
    print(ans)
    


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

n = int(input())
S = input()
k = n//2

for l in range(k, 0, -1):
    word = S[0:l]

    for i in range(n):
        if S[l+i:].find(word) >= 0:
            print(l)
            exit()

        if i + 2*l > n:
            break
        word = word[1:] + S[l+i]

print(0)

### FIXED CODE ###

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)
### BUGGY CODE ###

import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = {}
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    memo[k] = C(tmp, 2)
    ans += memo[k]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  if tmp == 2:
    print(ans - 1)
  if tmp > 2:
    print(ans - (memo[A[i]] - C(tmp-1, 2)))


### FIXED CODE ###

import math

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = tmp * (tmp - 1) // 2
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - tmp * (tmp - 1) // 2 + (tmp - 1) * (tmp - 2) // 2)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    if R // 2019 != L // 2019:
        ans = 0
    else:
        # ansLi = L % 2019
        # ansLj = (L+1) % 2019
        # ansL = ansLi * ansLj

        # ansRi = R % 2019
        # ansRj = (R-1) % 2019
        # ansR = ansRi * ansRj
        ansL = L*(L+1) % 2019
        ansR = R*(R-1) % 2019

        ans = min(ansL, ansR)

    return int(ans)

# print(main())

def search_all():
    if L - R >= 2019:
        return 0
    ans = float("inf")
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(i*j % 2019, ans)
    return ans

print(search_all())

### FIXED CODE ###

import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    if R // 2019 != L // 2019:
        ans = 0
    else:
        # ansLi = L % 2019
        # ansLj = (L+1) % 2019
        # ansL = ansLi * ansLj

        # ansRi = R % 2019
        # ansRj = (R-1) % 2019
        # ansR = ansRi * ansRj
        ansL = L*(L+1) % 2019
        ansR = R*(R-1) % 2019

        ans = min(ansL, ansR)

    return int(ans)

# print(main())

def search_all():
    if R // 2019 != L // 2019:
        return 0
    ans = float("inf")
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(i*j % 2019, ans)
            if ans == 0:
                break
    return ans

print(search_all())
### BUGGY CODE ###

import bisect

n = int(input())
l = sorted([int(li) for li in input().split()])

sum = 0
for i in range(n)[::-1]:
    for j in range(i)[::-1]:
        k = bisect.bisect_right(l,l[i]-l[j])
        sum += len(l[k:j])

print(sum)


### FIXED CODE ###

import bisect

n = int(input())
l = sorted([int(li) for li in input().split()])

sum = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_right(l,l[i]-l[j])
        sum += j-k if j>k else 0

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

S = input()
B = []
Nc = 0

while S != 'W'*len(S) and S != 'B'*len(S):
    if S.index('B') > S.index('W'):
        S = S.replace('W','B',S.index('B'))
        Nc += 1
    else:
        S = S.replace('B','W',S.index('W'))
        Nc += 1
print(Nc)

### FIXED CODE ###

S = input()
B = []
Nc = 0

for i in range(len(S)-1):
    if S[i] != S[i+1]:
        Nc += 1
print(Nc)
### BUGGY CODE ###

num, capacity = map(int, input().split())
dp = [0]*(capacity+1)

for _ in range(num):
    weight, value = map(int, input().split())
    for w in range(capacity,weight - 1,-1):
        if w < weight:
            continue
        else:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[capacity])

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

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

k = int(m/n)
ans = 1
for i in range(k):
    if m % (k-i) == 0:
        break
print(k-i)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

N,K=map(int,input().split())
num=list(map(float,input().split()))
#print(num)
answer=[]
for i in range(N):
    num[i]=(num[i]+1)/2
for i in range(N-K+1):
    ans=0
    for j in range(K):
        ans+=num[i+j]
    answer.append(ans)
a=max(answer)
print(a)

### FIXED CODE ###

N,K=map(int,input().split())
num=list(map(float,input().split()))
a=0
check=0
for i in range(N):
    num[i]=(num[i]+1)/2
    if i<K:
        check+=num[i]
a=check        
for i in range(N-K):
    ans=check-num[i]+num[K+i]
    if ans>a:
        a=ans
    check=ans  
print(a)
### BUGGY CODE ###

n=int(input())
s=[]
ans=0
for i in range(n):
  a=input()
  if a in s:
    s.remove(a)
    ans-=1
  else:
    s.append(a)
    ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = Counter([int(input()) for _ in range(N)])
ans = 0
for val in A.values():
    if val % 2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
word = [input() for i in range(n)]
test = list([x,0] for x in set(word))
sen = []

for i, num in enumerate(test):
  test[i][1] = word.count(num[0])

for i, num in enumerate(test):
  if(int(num[1]) == int(max(test, key=lambda x: x[1])[1])):
    sen.append(num[0])

print('\n'.join(sorted(sen)))


### FIXED CODE ###

from collections import Counter
n = int(input())
word = Counter([input() for i in range(n)]).most_common()
print('\n'.join(sorted([num[0] for num in word if int(num[1]) == word[0][1]])))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(H: int, W: int, M: int, h: "List[int]", w: "List[int]"):
    hDict = defaultdict(int)
    wDict = defaultdict(int)
    points = set()
    for i in range(M):
        hDict[h[i]]+=1
        wDict[w[i]]+=1
        points.add((h[i],w[i]))
    hArr = []
    wArr = []
    for hd in hDict:
        he = hDict[hd]
        hArr.append((-he,he,hd))
    for wd in wDict:
        he = wDict[wd]
        wArr.append((-he,he,wd))
    hArr.sort()
    wArr.sort()
    m = 0
    for h in hArr:
        for w in wArr:
            c = h[1] + w[1]
            if (h[2],w[2]) in points:
                c -= 1
            m = max(m,c)
    print(m)
    return


# Generated by 1.1.7.1 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()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    h = [int()] * (M)  # type: "List[int]"
    w = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        h[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(H, W, M, h, w)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(H: int, W: int, M: int, h: "List[int]", w: "List[int]"):
    hDict = defaultdict(int)
    wDict = defaultdict(int)
    points = set()
    for i in range(M):
        hDict[h[i]]+=1
        wDict[w[i]]+=1
        points.add((h[i],w[i]))
    hArr = []
    wArr = []
    for hd in hDict:
        he = hDict[hd]
        hArr.append((-he,he,hd))
    for wd in wDict:
        he = wDict[wd]
        wArr.append((-he,he,wd))
    hArr.sort()
    wArr.sort()
    m = 0
    hm = hArr[0][1]
    wm = wArr[0][1]
    # hm+wm or hm+wm -1
    for h in hArr:
        if h[1] < hm:
            break
        for w in wArr:
            if w[1] < wm:
                break
            c = h[1] + w[1]
            if (h[2],w[2]) in points:
                c -= 1
            else:
                print(c)
                return
            m = max(m,c)
    print(m)
    return


# Generated by 1.1.7.1 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()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    h = [int()] * (M)  # type: "List[int]"
    w = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        h[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(H, W, M, h, w)

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

N, = map(int, input().split())
xs = list(map(int, input().split()))
r = 0
for a in range(1, N-1):
    for b in range(1, N-2):
        if a <= b:
            continue
        if (N-1-a)%(a-b):
            continue
        n = (N-1-a)//(a-b)
        if a%(a-b) == 0:
            if a <= (a-b)*n:
                continue
        s = a
        t = xs[a]
        vs = set([a])
        for i in range(n):
            #t = max(0, t)
            s -= b
            t += xs[s]
            vs.add(s)
            s += a
            vs.add(s)
            t += xs[s]
        #print("k:%d, A:%d, B:%d"%(a-b,a,b))
        #print(vs, t)
        r = max(r, t)

print(r)


### FIXED CODE ###

N, = map(int, input().split())
xs = list(map(int, input().split()))
r = 0
for k in range(1, N):
    a = (N-1) % k
    b = a - k
    n = (N-1-a)//k
    if a <= k:
        a += k
    if a <= k:
        a += k

    for _ in range((N-1-a)//k):
        b = a - k
        n = (N-1-a)//k
        if a <= b:
            a += k
            continue
        if a%(a-b) == 0:
            if a <= (a-b)*n:
                a += k
                continue
    if a <= b or a >= N-1:
        continue
    s1 = a
    s2 = n * (a-b)
    t = xs[s1]
    ps = [(s1,t)]
    for i in range(n):
        s1 += a-b
        t += xs[s2]
        t = max(t,0)
        t += xs[s1]
        ps.append((s2,xs[s2]))
        ps.append((s1,xs[s1]))
        s2 -= a-b
    #print(ps, t)
    r = max(r, t)

print(r)
### BUGGY CODE ###

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

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    l1, l2 = 0, 0
    r1, r2 = N-1, N-1
    for j in range(i-1, -1, -1):
        if j in memo:
            l1 = j
            break
    else:
        l1 = -1
    for j in range(l1-1, -1, -1):
        if j in memo:
            l2 = j
            break
    else:
        l2 = -1
    for j in range(i+1, N):
        if j in memo:
            r1 = j
            break
    else:
        r1 = N
    for j in range(r1+1, N):
        if j in memo:
            r2 = j
            break
    else:
        r2 = N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    memo.append(i)

print(ans)


### FIXED CODE ###

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

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

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

import math
A, B, N = map(int, input().split())

def f(A, B, x):
  return math.floor((A * x) / B) - A * math.floor(x / B)

print(max([f(A, B, x) for x in range(1,min(N + 1, B + 1))]))

### FIXED CODE ###

import math
A, B, N = map(int, input().split())

def f(A, B, x):
  return math.floor((A * x) / B) - A * math.floor(x / B)

x = N if N < B else B - 1
print(f(A, B, x))
### BUGGY CODE ###

N, C = map(int,input().split())
D = [0] * C
for i in range(C):
    t = list(map(int,input().split()))
    D[i] = t
c = [0] * N
for i in range(N):
    t = list(map(int,input().split()))
    c[i] = t
Dsum = [0] * C
for k in range(C):
    ccc = [0, 0, 0]
    for i in range(N):
        for j in range(N):
            ccc[(i+j)%3] += D[c[i][j]-1][k]
    Dsum[k] = ccc
ans = 9876543210
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, Dsum[i][0]+Dsum[j][1]+Dsum[k][2])
print(ans)

### FIXED CODE ###

N, C = map(int,input().split())
D = []
for i in range(C):
    t = list(map(int,input().split()))
    D.append(t)
c = []
for i in range(N):
    t = list(map(int,input().split()))
    c.append(t)
Dsum = []
for k in range(C):
    ccc = [0, 0, 0]
    for i in range(N):
        for j in range(N):
            ccc[(i+j)%3] += D[c[i][j]-1][k]
    Dsum.append(ccc)
ans = 9876543210
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, Dsum[i][0]+Dsum[j][1]+Dsum[k][2])
print(ans)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
f = 0
for i in range(a,b+1):
  if i%c != 0 and i%d != 0:
    f += 1
print(f)

### FIXED CODE ###

import fractions as f
a,b,c,d = map(int,input().split())
i = abs((a-1)//c-b//c)
j = abs((a-1)//d-b//d)

def lcm(x,y):
  return (x*y)//f.gcd(x,y)
l = lcm(c,d)
k = abs((a-1)//l-b//l)
print(b-a+1-(i+j-k))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(int(input()))
a=set(b)
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    b=dp[0]
    for i in range(1,n):
        dpi=dp[i]
        for j in range(1,m):
            if s[i]==t[j]:
                dpi[j]=b[j-1]+1
            else:
                dpi[j]=max(b[j],dpi[j-1])
        b=dpi
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

### FIXED CODE ###

s=' '+input()
t=' '+input()
dp=[[0]*len(t)for _ in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=[]
i,j=len(s)-1,len(t)-1
while dp[i][j]:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i])
        i-=1
        j-=1
print(''.join(ans[::-1]))
### BUGGY CODE ###

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

a = [0] * (N + 1)
r = [0] * P

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[a[i] % P] += 1
    r[0] += 1
    ans = 0
    for i in range(P):
        ans += r[i] * (r[i] - 1) // 2
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)



### FIXED CODE ###

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

a = [0] * (N + 1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = ((int(S[N-i])*tenfactor+a[i-1])%P)
        tenfactor*=10
        tenfactor%=P

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

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

def main():
    S=input()
    MOD=10**9+7
    dp=[[0]*13 for _ in range(1+len(S))]
    dp[0][0]=1
    r=1
    for i in range(len(S)):
        s=S[-1-i]
        if s=="?":
            for j in range(10):
                rem=(j*r)%13
                for k in range(13):
                    dp[i+1][(k+rem)%13]+=dp[0][k]
        else:
            rem=(int(s)*r)%13
            for k in range(13):
                dp[i+1][(k+rem)%13]+=dp[0][k]
        for l in range(13):
            dp[i+1][l]%=MOD
        dp[0]=dp[i+1]
        r=(r*10)%13
    print(dp[len(S)][5])
if __name__=="__main__":
    main()

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
r=1
for i in range(len(S)):
    new_dp=[0]*13
    s=S[-1-i]
    if s=="?":
        for j in range(10):
            rem=(j*r)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
    else:
        rem=(int(s)*r)%13
        for k in range(13):
            new_dp[(k+rem)%13]+=dp[k]
    for l in range(13):
        new_dp[l]%=MOD
    dp=new_dp
    r=(r*10)%13
print(dp[5])