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

import sys
from heapq import heapify, heappop

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = input()
    k = int(input())
    n = len(S)

    SS = set()
    for i in range(n):
        ss = [S[i]]
        SS.add("".join(ss))
        for j in range(i + 1, n):
            ss.append(S[j])
            SS.add("".join(ss))

    SS = list(SS)
    heapify(SS)
    for _ in range(k):
        res = heappop(SS)
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
from heapq import heapify, heappop

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = input()
    k = int(input())
    n = len(S)

    SS = set()
    for i in range(n):
        ss = S[i]
        SS.add(ss)
        for j in range(i + 1, min(n, i + k)):
            ss += S[j]
            SS.add(ss)

    SS = list(SS)
    heapify(SS)
    for _ in range(k):
        res = heappop(SS)
    print(res)


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

# -*- coding: utf-8 -*-

N = int(input())

result = 0
for n in range(1,N+1):
    result += sum([n*i for i in range(1, int(N/n)+1)])

print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

def sum_inc(n):
    return int(n*(n+1)/2)

half = int(N/2)+1

each_result = [n*sum_inc(int(N/n)) for n in range(1,half)]

print(sum(each_result)+sum_inc(N) - sum_inc(half-1))
### BUGGY CODE ###

N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=1

DP = [1]
dic = {}      
Sum = 1

for i in range(len(C)):  
    Sum += dic.get(C[i],0)
    Sum %= 10**9+7
    DP.append(Sum)                               
    dic[C[i]] = Sum   
print(Sum)             

### FIXED CODE ###

N = int(input())
C = [int(input()) for _ in range(N)]
C = [x for x,y in zip(C[:-1],C[1:]) if x!=y] + [C[-1]]

DP = [1]
dic = {}

for i in range(len(C)):   
    DP.append((DP[-1]+dic.get(C[i],0))%(10**9+7))    
    dic[C[i]] = DP[-1]
print(DP[-1])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
m=min(a)
n=max(a)
c=[]
for i in range(m,n+1):
  count=0
  for j in range(N):
    if i-1<=a[j]<=i+1:
      count+=1
  c.append(count)
print(max(c))

### FIXED CODE ###

from collections import Counter
N=int(input())
a=list(map(int,input().split()))
for i in range(N):
  a.append(a[i]+1)
  a.append(a[i]-1)
c=Counter(a).most_common()
print(c[0][1])
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(1000000)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n in popcount:
        return popcount[n]
    else:
        popcount[n] = gpc(n // 2) + (n & 1)
        return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    else:
        pc = gpc(Xk)
        if (Xk, pc) in solutions:
            return solutions[Xk, pc]
        else:
            count = 1 + sol(Xk % pc)
            solutions[Xk, pc] = count
            return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    iX = int(X, 2)

    for k in range(N - 1, -1, -1):
        Xk = iX ^ (1 << k)
        ans = sol(Xk)
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1") # pc
mod_p1 = int(B, 2) % (B_1 + 1) # pc + 1
if B_1 != 1:
    mod_m1 = int(B, 2) % (B_1 - 1) # pc - 1

# 小さい数字は直接計算しても一瞬
def calc_small(n, count):
    count += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return count
    else:
        return calc_small(mod, count)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue

    # はBiが1か0かで，元のmodから差分計算できる
    if B[i] == '1':
        # 反転して-する場合 (mod PC - 1)
        mod = (mod_m1 - pow(2, N - i - 1, B_1 - 1)) % (B_1 - 1)
    else:
        # 反転して+する場合 (mod PC + 1)
        mod = (mod_p1 + pow(2, N - i - 1, B_1 + 1)) % (B_1 + 1)
    count = 1
    if mod == 0:
        print(count)
    else:
        print(calc_small(mod, count))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w-1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])


### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j),k)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

def dp(i,j):
    if i >= j:
        return 0
    if (i,j) not in memo:
        ans = float("inf")
        for k in range(i,j):
            temp = dp(i,k) + dp(k+1,j) + p[j+1] - p[i]
            ans = min(ans,temp)
        memo[i,j] = ans
    return memo[i,j]
print(dp(0,n-1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for _ in range(n+1)]
s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = s[j] - s[i] + min(dp[i][k] + dp[k][j] for k in range(i+1, j))
print(dp[0][n])
### BUGGY CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))

dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])


### FIXED CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])
### BUGGY CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
d = []
for i in range(n):
    k = readi()
    d.append(k)
p = []
g = -1
for i in range(n - 1):
    t = d[i]
    k = max(d[i+1:n])
    print(max(k, g))
    g = max(t, g)
print(max(d[0],g))

### FIXED CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
d = []
h = []
for i in range(n):
    k = readi()
    d.append(k)
    heapq.heappush(h,-k)
t1 = -heapq.heappop(h)
t2 = -1
if h:
    t2 = -heapq.heappop(h)
if n == 1:
    print(d[0])
else:
    for i in range(n):
        if d[i] == t1:
            print(t2)
        else:
            print(t1)
### BUGGY CODE ###

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

#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

Slist = list(S)

count = 0
for i in range(len(Slist)):
    for j in range(i+1, len(Slist)):
        for k in range(j+1, len(Slist)):
            if(Slist[i] == Slist[j]):
                break
            notEqualColor = (Slist[j] == Slist[k] or Slist[k] == Slist[i])
            notEqualDistance = (j - i == k - j)

            if((notEqualColor or notEqualDistance) == False):
                count += 1

print(count)


### FIXED CODE ###

import collections

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

CountRGB = collections.Counter(S)

ans = CountRGB["R"] * CountRGB["G"] * CountRGB["B"]

tmp = 0
for i in range(N-2):
    for j in range(i+1, N-1):

        if(2 * j - i > N - 1):
            break

        checker = []
        checker.append(S[i])
        checker.append(S[j])
        checker.append(S[2 * j - i])

        c = collections.Counter(checker)

        if(c["R"] == 1 and c["G"] == 1 and c["B"] == 1):
            tmp +=1

print(ans - tmp)
### BUGGY CODE ###

from copy import deepcopy
import sys
def main():
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  grid=[list(input()) for _ in range(h)]
  def score(t):
    total=0
    for i in range(1,h):
      for j in range(w-1):
        cnt=1
        ten=int(gc[i][j])
        while gc[i][j+1]==gc[i][j]:
          cnt+=1
          j+=1
          if j==w-1:
            break
        if cnt>=k:
          total+=2**t*(ten*cnt)
          gc[i][j-cnt+1:j+1]=['0']*cnt
    return total
  def upd():
    while 1:
      ok=True
      for i in range(1,h):
        for j in range(w):
          if gc[i][j]=='0' and gc[i-1][j]!='0':
            x=gc[i-1][j]
            gc[i-1][j]='0'
            gc[i][j]=x
            ok=False
      if ok:
        return
  ans=0
  for i in range(1,h):
    for j in range(w):
      gc=deepcopy(grid)
      gc[i][j]='0'
      t=0
      res=0
      while 1:
        upd()
        total=score(t)
        if total==0:
          break
        t+=1
        res+=total
      ans=max(ans,res)
  return print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

from copy import deepcopy
import sys
def main():
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  grid=[]
  for _ in range(h):
    s=input().rstrip()
    s=list(s)
    s=list(map(int,s))
    grid.append(s)
  def score(t):
    total=0
    for i in range(1,h):
      for j in range(w-1):
        cnt=1
        ten=gc[i][j]
        while gc[i][j+1]==gc[i][j]:
          cnt+=1
          j+=1
          if j==w-1:
            break
        if cnt>=k:
          total+=2**t*(ten*cnt)
          gc[i][j-cnt+1:j+1]=[0]*cnt
    return total
  def upd():
    while 1:
      ok=True
      for i in range(1,h):
        for j in range(w):
          if gc[i][j]==0 and gc[i-1][j]!=0:
            x=gc[i-1][j]
            gc[i-1][j]=0
            gc[i][j]=x
            ok=False
      if ok:
        return
  ans=0
  for i in range(1,h):
    for j in range(w):
      gc=deepcopy(grid)
      gc[i][j]=0
      t=0
      res=0
      while 1:
        upd()
        total=score(t)
        if total==0:
          break
        t+=1
        res+=total
      ans=max(ans,res)
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

def quest_d():
    N = int(input())
    S = input()

    r_index = []
    g_index = []
    b_index = []
    for index in range(len(S)):
        if S[index] == 'R':
            r_index.append(index)
        elif S[index] == 'G':
            g_index.append(index)
        else:
            b_index.append(index)
    if len(r_index) * len(g_index) * len(b_index) == 0:
        print(0)
        return

    i = 0
    sum = 0
    while i < len(S):
        a = S[i]
        j = i
        while j < len(S) - 1:
            j += 1
            if S[j] == a:
                continue

            l = 2 * j - i
            b = S[j]
            k = j
            while k < len(S)- 1:
                k += 1
                if S[k] == a or S[k] == b or l == k:
                    continue
                sum += 1
        i += 1
    print(sum)

if __name__ == '__main__':
    quest_d()


### FIXED CODE ###

def combi_three(n):
    if n < 3:
        return 0
    else:
        return int((n * (n - 1) * (n - 2)) / 6)

def quest_d():
    N = int(input())
    S = input()

    index_dict = {'R':0, 'G':0, 'B':0 }
    for index in range(N):
        index_dict[S[index]] = index_dict[S[index]] + 1

    if index_dict['R'] * index_dict['G'] * index_dict['B'] == 0:
        print(0)
        return

    rrr = combi_three(index_dict['R'])
    ggg = combi_three(index_dict['G'])
    bbb = combi_three(index_dict['B'])
    rrg = combi_three(index_dict['R'] + index_dict['G'])
    ggb = combi_three(index_dict['G'] + index_dict['B'])
    bbr = combi_three(index_dict['B'] + index_dict['R'])

    i = 0
    sum = 0
    while i < N:
        a = S[i]
        j = i
        while j < N - 1:
            j += 1
            if S[j] == a:
                continue

            k = 2 * j - i
            if k < N:
                b = S[j]
                if S[k] != a and S[k] != b:
                    sum += 1
        i += 1
    print(combi_three(N) - sum - rrg - bbr - ggb + rrr + ggg + bbb)

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

terms = [int(i) for i in input().split(" ")]
scores = [int(i) for i in input().split(" ")]

N = terms[0]
K = terms[1]

baseScore = 1

for i in range(K):
    baseScore *= scores[i]

tempScore = 1
for i in range(K,N):
    for j in range(K):
        tempScore *= scores[i - j]
    if tempScore > baseScore:
        print('Yes')
    else:
        print('No')
    baseScore = tempScore
    tempScore = 1


### FIXED CODE ###

terms = [int(i) for i in input().split(" ")]
scores = [int(i) for i in input().split(" ")]

N = terms[0]
K = terms[1]

tempScore = []
scoreSet = []

for i in range(N-K):
    if scores[i] < scores[i+K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N=int(input())
list_A=[int(A) for A in input().split()]
list_A.insert(0,0)
list_A.append(0)
for i in range(1,N+1):
  money=0
  list_B=list_A.copy()
  del list_B[i]
  for k in range(1,N+1):
    money+=abs(list_B[k]-list_B[k-1])
  print(money)
    

### FIXED CODE ###

N=int(input())
list_A=[int(A) for A in input().split()]
list_A.insert(0,0)
list_A.insert(N+1,0)
money=0
for i in range(N+1):
  money+=abs(list_A[i+1]-list_A[i])
for i in range(1,N+1):
  Money=money-abs(list_A[i]-list_A[i-1])-abs(list_A[i+1]-list_A[i])+abs(list_A[i+1]-list_A[i-1])
  print(Money)
### BUGGY CODE ###

def solve():
    N = int(input())
    P = [list(map(int, input().split())) for i in range(N)]
    MOD = 998244353

    P.sort()

    Y = [y for x, y in P]

    def compress(X):
        *XS, = set(X)
        XS.sort()
        return {e: i for i, e in enumerate(XS)}
    MY = compress(Y)

    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    pow2 = [1]*N
    r = 1
    for i in range(1, N):
        pow2[i] = r = r * 2 % MOD

    ans = 0
    for i, y in enumerate(Y):
        y = MY[y]
        v1 = get(y+1); v0 = y - v1
        w1 = i - v1; w0 = (N - y - 1) - w1
        add(y+1, 1)
        p1 = pow2[v1] - 1; p0 = pow2[v0] - 1
        q1 = pow2[w1] - 1; q0 = pow2[w0] - 1
        ans += 2 * ((p1+1)*(p0+1) % MOD)*((q1+1)*(q0+1) % MOD) % MOD
        ans -= (1 + p0 + p1 + q0 + q1 + p0 * (p1 + q0) + (p1 + q0) * q1) % MOD
    print(ans % MOD)
solve()

### FIXED CODE ###

import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 998244353

    N = int(readline())
    P = [list(map(int, readline().split())) for i in range(N)]

    P.sort()

    Y = [y for x, y in P]

    def compress(X):
        *XS, = set(X)
        XS.sort()
        return list(map({e: i for i, e in enumerate(XS)}.__getitem__, X))
    Y = compress(Y)

    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def gen(add, get):
        pow2 = [1]*N
        r = 1
        for i in range(1, N):
            pow2[i] = r = r * 2 % MOD

        for i, y in enumerate(Y):
            v1 = get(y+1); v0 = y - v1
            w1 = i - v1; w0 = (N - y - 1) - w1
            add(y+1, 1)
            p1 = pow2[v1]; p0 = pow2[v0]
            q1 = pow2[w1]; q0 = pow2[w0]
            yield (2 * (p1*p0 % MOD)*(q1*q0 % MOD) % MOD) - (1 - p0 - p1 - q0 - q1 + (p0 + q1) * (p1 + q0)) % MOD
    write("%d\n" % (sum(gen(add, get)) % MOD))
solve()
### BUGGY CODE ###

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

count = []
for i in range(n):
    count.append(s.count(s[i]))

a = max(count)
ans = []
for i in range(n):
    if count[i] == a:
        if not(s[i] in ans):
            ans.append(s[i])

ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

import collections
n = int(input())
s = list(input() for i in range(n))
counted = collections.Counter(s)

m = max(counted.values())
chars = [key for key, value in counted.items()
             if value == m]
chars.sort()
for i in range(len(chars)):
    print(chars[i])
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

print(b//x - (a-1)//x)
### BUGGY CODE ###

N = int(input())
s = [input().split() for i in range(N)]
s_af = [""]*N
for i in range(N):
    s[i] = list(s[i][0])
    s[i].sort()
    for k in range(10):
        s_af[i] += s[i][k]
s_af.sort()
count = 0
for i in range(N):
    for j in range(i+1,N):
        if s_af[i] == s_af[j]:
            count += 1
        else:
            break
print(count)

### FIXED CODE ###

N = int(input())
s = [input().split() for i in range(N)]
for i in range(N):
    s[i] = list(s[i][0])
    s[i].sort()
    s[i] = ''.join(map(str, s[i]))
s.sort()
count = 0
ren = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        count += 1+ren
        ren += 1
    else:
        ren = 0
print(count)
### BUGGY CODE ###

class Union:
    def __init__(self, n):
        self.root = True
        self.parent = n

    def update(self, n):
        self.root = False
        self.parent = n

def search(n):
    global A

    while not A[n-1].root:
        n = A[n-1].parent

    return n

N, M = list(map(int, input().split()))
A = [Union(i) for i in range(1, N+1)]
nums = [i for i in range(1, N+1)]

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root = search(X)
    Y_root = search(Y)

    if X_root != Y_root:
        A[Y_root-1].update(X_root)
        nums.remove(Y_root)

print(len(nums))

### FIXED CODE ###

def search(n):
    idx = n
    while A[n-1] != n:
        n = A[n-1]
    A[idx-1] = n

    return n

N, M = list(map(int, input().split()))
A = [i for i in range(1, N+1)]
ans = 0

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root, Y_root = search(X), search(Y)

    if X_root != Y_root:
        A[X_root-1] = Y_root
        ans += 1

print(N-ans)
### BUGGY CODE ###

from bisect import bisect_left
from math import sqrt
S = int(input())
inf = 10**9
for X in range(max(0, int(sqrt(max(0, S-6*10**11)))), int(sqrt(S))+1):
    Y = S-X*X
    for i in range(1, int(sqrt(Y)+1)):
        if Y % i == 0 and 0 <= Y//i <= inf:
            if abs(X*X-Y) == S:
                print(0, 0, i, X, X, Y//i)
                quit()
for X in range(int(sqrt(S)), int(sqrt(S+10**11))):
    Y = X*X-S
    for i in range(1, int(sqrt(max(0,Y))+1)):
        if Y % i == 0 and 0 <= Y//i <= inf:
            if abs(X*X-Y) == S:
                print(0, 0, i, X, X, Y//i)
                quit()


### FIXED CODE ###

S = int(input())
t = 10**9
print(0, 0, 1, t, S//t+(S%t!=0), (t-S%t)%t)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())

p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = list(map(int,input().split()))


for i in range(len(r)):
    p_min = min(p)
    q_min = min(q)
    r_max = max(r)

    if p_min > r_max and q_min > r_max:
        break

    p_min_diff = r_max - p_min
    q_min_diff = r_max - q_min

    if p_min_diff > q_min_diff and p_min_diff > 0:
        p.remove(p_min)
        p.append(r_max)
        r.remove(r_max)
    elif q_min_diff > p_min_diff and q_min_diff > 0:
        q.remove(q_min)
        q.append(r_max)
        r.remove(r_max)

print(sum(p) + sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    len_S = len(S)
    dp = np.array([[0] * 13 for _ in range(len_S + 1)])
    dp[0][0] = 1

    for i in range(len_S):
        S_i = S[i]
        for j in range(13):
            if S_i == '?':
                for k in range(10):
                    dp[i+1][(j*10+k)%13] += dp[i][j]
                    dp[i+1][(j*10+k)%13] %= MOD
            else:
                dp[i+1][(j*10+int(S_i))%13] += dp[i][j]
                dp[i+1][(j*10+int(S_i))%13] %= MOD

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    len_S = len(S)
    dp = [[0] * 13 for _ in range(len_S + 1)]
    dp[0][0] = 1

    for i in range(len_S):
        S_i = S[i]
        for j in range(13):
            if S_i == '?':
                for k in range(10):
                    dp[i+1][(j*10+k)%13] += dp[i][j]
                    dp[i+1][(j*10+k)%13] %= MOD
            else:
                dp[i+1][(j*10+int(S_i))%13] += dp[i][j]
                dp[i+1][(j*10+int(S_i))%13] %= MOD

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

if __name__ == '__main__':
    resolve()