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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode().rstrip()

ans = 0
for i in range(1000):
    i_ = str(i).zfill(3)
    idx = 0

    for s in S:
        if s == i_[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode().rstrip()

ans = 0
for i in range(1000):
    i_ = '{:>03}'.format(i)
    idx = 0

    for s in S:
        if s == i_[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

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

a=int(input())
b=list(map(int,input().split()))
c=0
if a==0:
  print(0)
else:
  for i in range(a-1):
    while b[i]>b[i+1]:
      b[i+1]=b[i+1]+1
      c=c+1
  print(c)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c=0
for i in range(a-1):
  if b[i]>b[i+1]:
    c=c+b[i]-b[i+1]
    b[i+1]=b[i]
print(c)
### BUGGY CODE ###

import math
import copy
from queue import Queue

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m) :
    s[s.index(max(s))] = math.floor(max(s)/2)

print(sum(s))

### FIXED CODE ###

import math
import copy
from queue import Queue
import heapq

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

s = list(map(lambda x: x*(-1), s))
heapq.heapify(s)

for i in range(m) :
    heapq.heappush(s, math.ceil(heapq.heappop(s)/2))

print(sum(s)*(-1))
### BUGGY CODE ###

input()
A = list(map(int,input().split(' ')))
if 0 in A:
    print(0)
else:
    x=A[0]
    for a in A[1::]:
        x=x*a
    if x > 1000000000000000000:
        print(-1)
    else:
        print(x)

### FIXED CODE ###

N = input()
A = list(map(int,input().split(' ')))
if 0 in A:
    print(0)
    exit()
x = 1
for a in A:
    x *= a
    if x > 1000000000000000000:
        print(-1)
        exit()
print(x)
### BUGGY CODE ###

N, K = map(int, input().split())
S = []

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))
  
S.sort()

DP =[0]*N
DP[0] = 1

for i in range(N-1):
  if i + S[0] >= N:
    break
  for j in S:
    if i+j<N:
      DP[i+j] += DP[i]
    else:
      break

print(DP[-1]%998244353)

### FIXED CODE ###

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

L = []
R = []

for _ in range(K):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print((dp[N]-dp[N-1])%998244353)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
A = 0
for i in range(n-k+1):
    exp = sum(p[i:i+k])
    if ans < exp:
        ans = exp 
        A = (exp+k)/2
print(A)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
exp = sum(p[0:k])
ans = exp
for i in range(n-k):
  exp = exp-p[i]+p[i+k]
  #print(ans, exp)
  if ans<exp:
    ans = exp
    #print("ans", exp, ans)
print((ans+k)/2)
### BUGGY CODE ###

h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

ans = 0
for x in xs:
    for y in ys:
        if (y, x) in points:
            ans = max(ans, count_h[y] + count_w[x] - 1)
        else:
            ans = max(ans, count_h[y] + count_w[x])
print(ans)



### FIXED CODE ###

h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

    
ans = ch_max + cw_max
if len(ys) * len(xs) <= m:
    def _find():
        for x in xs:
            for y in ys:
                if (y, x) not in points:
                    return True
        return False
    if not _find():
        ans -= 1
print(ans)
### BUGGY CODE ###

import math
import numpy

def is_prime(n):
    if (n==1):
        return 0
    for i in range(2,int(math.sqrt(n))+1):
        if (n % i == 0):
            return 0
    return 1

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (is_prime(i) and is_prime((i+1)/2)):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])

### FIXED CODE ###

import math
import numpy

def is_prime(n):
    if (n==1):
        return 0
    if (n==2):
        return 1
    for i in range(3,int(math.sqrt(n))+1,2):
        if (n % i == 0):
            return 0
    return 1

prime = [0]*(10**5+1)
for i in range(1,10**5+1,2):
    prime[i] = is_prime(i)
prime[2] = 1

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (prime[i] and prime[int((i+1)/2)]):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])
### BUGGY CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcmCalc(x, y):
	return int((x * y) / gcd(x, y))

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

lcm = lcmCalc(n, m)

str1 = ""
for i in range(lcm):
	str1 += "-"

for i in range(n):
	index = int(i * lcm / n + 1)
	str1 = str1[:index] + s[i] + str1[index+1:]

flg = 0
for i in range(m):
	index = int(i * lcm / m + 1)
	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
		print("-1")
		flg = 1
		break

if flg == 0:
	print(lcm)

### FIXED CODE ###

def gcd(a, b):
	if a > b:
		a, b = b, a
	if a % b == 0:
		return b
	while a % b != 0:
		c = a% b
		a = b
		b = c
	else:
		return c

def lcmCalc(x, y):
	return (x * y) // gcd(x, y)

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

lcm = lcmCalc(n, m)

# str1 = ""
# for i in range(lcm):
# 	str1 += "-"

flg = 0
for i in range(n):
	index = i * lcm // n + 1
	if (index - 1) % (lcm // m) == 0:
		j = (index - 1) // (lcm // m)
		if s[i] != t[j]:
			print("-1")
			flg = 1
			break
if flg == 0:
	print(lcm)


# 	str1 = str1[:index] + s[i] + str1[index+1:]

# flg = 0
# for i in range(m):
# 	index = i * lcm // m + 1
# 	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
# 		print("-1")
# 		flg = 1
# 		break

# if flg == 0:
# 	print(lcm)
### BUGGY CODE ###

N=int(input())
R=[[] for i in range(N)]
a=[]
b=[]
L=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    R[a[i]].append(b[i])

for i in range(N-1):
    L.append([len(R[i]),i])

L.sort(reverse=True)

K=L[0][0]

for i in range(N-1):
    if L[i][0]!=K:break
    if L[i][1] in b:
        K+=1
        break

print(K)

C=[[] for i in range(K)]
for i in range(N-1):
    for k in range(K):
        if (a[i] in C[k]) or (b[i] in C[k]):continue
        else:
            print(k+1)
            C[k].append(a[i])
            C[k].append(b[i])
            break



### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    G[ai-1].append(bi-1)
    G[bi-1].append(ai-1)

k=[0]*N

from collections import deque

q=deque([0])
visited=[0]*N
ans={}
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    visited[x]=1
    cnt=1
    for i in G[x]:
        if visited[i]!=0:continue
        if p[x]==cnt:
            cnt+=1
        ans[(x,i)]=cnt
        ans[(i,x)]=cnt

        p[i] = cnt
        cnt += 1
        kmx=max(kmx,cnt-1)
        q.append(i)

print(kmx)
for i in range(N-1):
    print(ans[(a[i],b[i])])
### BUGGY CODE ###

N = int(input())
lst = list(map(str, input().split()))
for i in range(N):
    idx = lst.index((str(i+1)))
    print(idx+1,end=" ")


### FIXED CODE ###

N = int(input())
lst = list(map(int, input().split()))
a = [0]*N
for i,j in enumerate(lst):
    a[j-1] = str(i+1)

print(" ".join(a))
### BUGGY CODE ###

n, k = (int(i) for i in input().split())
a = [int(i)-1 for i in input().split()]

count_list = [0]*n
for i in range(n):
    count_list[i] = a.count(i)

print(n-sum(sorted(count_list, reverse=True)[:k]))

### FIXED CODE ###

n, k = (int(i) for i in input().split())
a = [int(i)-1 for i in input().split()]

import collections
c = collections.Counter(a)
values, counts = zip(*c.most_common(k))
print(n-sum(counts))
### BUGGY CODE ###

import sys
finput = sys.stdin.readline
n,m = map(int, finput().split())

tasks = [0]*n
rewards = [0]*n
total = [0]*(m+1)

for i in range(n):
    tasks[i],rewards[i] = [int(j) for j in finput().split()]

que = [idx for idx, item in enumerate(rewards) if item == max(rewards)]

day = 0

while que:
    subtasks = [tasks[i] for i in que]
    while subtasks:
        t = max(subtasks)
        idx = subtasks.index(t)
        if t+day <= m:
            total[t+day:m+1] = [total[i]+rewards[que[idx]] for i in range(t+day,m+1)]
            day += 1
        del subtasks[idx]
        del tasks[que[idx]]
        del rewards[que[idx]]
        del que[idx]
    if rewards==[]:
        break
    if day+min(tasks)>m:
        break
    que += [idx for idx, item in enumerate(rewards) if item == max(rewards)]

print(max(total))


### FIXED CODE ###

import heapq
import sys

finput = sys.stdin.readline

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

q = [[] for i in range(m)]

for i in range(n):
    a,b = [int(j) for j in finput().split()]
    if a>m:
        continue
    q[a-1].append(-b)

hq = []
heapq.heapify(hq)
ans = 0
for i in range(m):
    if len(hq)==0 and len(q[i])==0:
        continue
    for j in range(len(q[i])):
        heapq.heappush(hq, q[i][j])
    ans += heapq.heappop(hq)

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

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

i = 1
while i <= n:
    print(A.count(i))
    i += 1

### FIXED CODE ###

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

R = [0 for i in range(n)]
for i in range(n-1):
    R[A[i]-1] += 1

for i in range(n):
    print(R[i])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

list = []
for i in range(x):
    for j in range(y):
        list.append(a[i]+b[j])
list.sort(reverse = True)
list = list[:k]

list1 = []
for i in range(len(list)):
    for j in range(z):
        list1.append(list[i]+c[j])
list1.sort(reverse = True)
list1 = list1[:k]

for i in range(k):
    print(list1[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
b = sorted(list(map(int, input().split())), reverse = True)
c = sorted(list(map(int, input().split())), reverse = True)

list = []
for aa in a:
    for bb in b:
        list.append(aa+bb)
list.sort(reverse = True)
list = list[:k]

list1 = []
for ab in list:
    for cc in c:
        list1.append(ab+cc)
list1.sort(reverse = True)
list1 = list1[:k]

for i in range(k):
    print(list1[i])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	num = 1
	for i in range(1,length):
		num = (10*num) % 13
		if s[-i-1] != '?':
			num2 = num * int(s[-i-1]) % MOD
			for j in range(13):
				dp[i][(num2+j)%13] = dp[i-1][j] % MOD
		else:
			for j in range(10):
				for k in range(13):
					dp[i][(num*j+k)%13] += dp[i-1][k] % MOD

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

if __name__ == '__main__':
	main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

from itertools import combinations, product
from functools import reduce
import bisect as bs
from collections import namedtuple

Area = namedtuple('Area', ['xinf', 'xsup', 'yinf', 'ysup'])

def tuple_int(iterable):
    return tuple(map(int, iterable.split()))

def insert_xy(line):
    x, y = map(int, line.split())
    X.insert(bs.bisect_left(X,x), x)
    Y.insert(bs.bisect_left(Y,y), y)
    return X, Y

def S_with_K_plots(X, Y, K):
    result = []
    for x, y in product(combinations(X,2), combinations(Y,2)):
        area = Area(xinf=min(x),xsup=max(x),yinf=min(y),ysup=max(y))
        S = (area.xsup-area.xinf)*(area.ysup-area.yinf)
        if count_plots(area) == K:
            result.append(S)
    return result

def count_plots(area):
    is_in_the_area = lambda x: is_in_area(x, area)
    return sum(map(is_in_the_area, plots))

def is_in_area(plot, area):
    between = lambda a, b, c:True if b <= a <= c else False
    x, y = plot
    x1, x2, y1, y2 = area
    if between(x, x1, x2) and between(y, y1, y2):
        return 1
    else:
        return 0

if __name__ == '__main__':
    with open(0) as f:
        N, K = map(int, f.readline().split())
        data = f.readlines()
    plots = list(map(tuple_int, data))
    X, Y = [], []
    for x, y in plots:
        X.append(x); Y.append(y)
    print(min(S_with_K_plots(X, Y, K)))

### FIXED CODE ###

N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1 in Y:
        y2 = [y for x,y in Plot if x1 <= x <= x2 and y1 <= y]
        if len(y2) < K:
            break
        y2.sort()
        S = (x2-x1)*(y2[K-1]-y1)
        ans = min(ans, S)
print(ans)
### BUGGY CODE ###

n = int(input())
ps = list(map(int, input().split()))
m = 1
fps = []
for i in range(1, n):
  fps.append(ps[i-1])
  if min(fps) > ps[i]:
    m += 1
print(m)

### FIXED CODE ###

n = int(input())
ps = list(map(int, input().split()))
fps = [ps[0]]
for i in range(1,n):
  if fps[len(fps)-1] > ps[i]:
    fps.append(ps[i])
print(len(fps))
### BUGGY CODE ###

from operator import itemgetter
from bisect import bisect_left, bisect_right
import sys

def main():
    n = int(sys.stdin.readline())
    keys = map(lambda i:map(int,sys.stdin.readline().split())+[i],xrange(n))
    keys.sort()

    q = int(sys.stdin.readline())
    for i in xrange(q):
        x0,x1,y0,y1 = map(int,sys.stdin.readline().split())
        key_x,key_y,ids = zip(*keys)
        interval = xrange(bisect_left(key_x,x0),bisect_right(key_x,x1))
        if interval:
            key1 = map(lambda j:[key_x[j],key_y[j],ids[j]],interval)
            key1.sort(key=itemgetter(1))
            key_x,key_y,ids = zip(*key1)
            interval = xrange(bisect_left(key_y,y0),bisect_right(key_y,y1))
            if interval:
                ids = map(lambda j:ids[j],interval)
                ids.sort()
                map(lambda x: sys.stdout.write("{}\n".format(x)),ids)
        print ("")

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

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

def dfs(G, v, p, d):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1)


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
root = T
dfs(GT, root, -1, 0)
dt = depth.copy()

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
root = A
dfs(GA, root, -1, 0)
da = depth.copy()

def dfs2(GT, v, p):
    for nv in GT[v]:
        if nv == p:
            continue
        if dt[nv] <= da[nv]:
            maxd[0] = max(maxd[0], da[nv])
        else:
            continue
        dfs2(GT, nv, v)


maxd = [da[T]]
root = T
dfs2(GT, root, -1)
print(maxd[0]-1)

### FIXED CODE ###

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

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

ans = 0
for t, a in zip(dt, da):
    if t <= a:
        ans = max(ans, a)
print(ans-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#-------------------------------------
v = int(input())
n = [i+1 for i in range(v)]
p = n[::-1]

ammount = 0
for i in range(v):
    ammount += n[i]

print(ammount-v)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#-------------------------------------
n = int(input())
print((n+1) * (n//2) + (n%2)*(n//2+1) - n)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
i=0
ans=[0]
while True:
    if a[i] in ans:
        print(-1)
        break
    if a[i]==2:
        print(len(ans))
        break
    ans.append(a[i])
    i=a[i]-1

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
now=0
c=0
while True:
    if now==1:
        print(c)
        break
    if c>=n:
        print(-1)
        break
    c+=1
    now=a[now]-1
### BUGGY CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))


dp = [[0,0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    if c == "D":
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
    if c == "M":
        dp[i][1] = dp[i-1][1] + dp[i-1][0]
        dp[i][3] = dp[i-1][3] + 1
    else:
        dp[i][1] = dp[i-1][1]
        dp[i][3] = dp[i-1][3]
    if c == "C":
        dp[i][2] = dp[i-1][2] + dp[i-1][1]
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
#            print(i, i-1, i-q, q)
#            print(dp[i-1], dp[ll]) 
            As[j] += dp[i-1][1] - dp[ll][1] - (dp[ll][0]*(dp[i-1][3]-dp[ll][3]))
    else:
        dp[i][2] = dp[i-1][2]
for a in As:
    print(a)
#print(dp)


### FIXED CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)
### BUGGY CODE ###

S = input()
MOD = 10**9+7
dp = [0,]*13
next_dp = [0,]*13
dp[0] = 1
for i, s in enumerate(reversed(S)):
    for j, d in enumerate(dp):
        if s == '?':
            for k in range(10):
                next_dp[(j+k*(10**i))%13] += d
        else:
            next_dp[(j+int(s)*(10**i))%13] += d
    for j, d in enumerate(next_dp):
        next_dp[j] = d % MOD
    dp = next_dp
    next_dp = [0,]*13
print(dp[5])

### FIXED CODE ###

S = input()[::-1]
MOD = 10**9+7
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]
p = 1
for i, s in enumerate(S):
    nx = [0,]*13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
    p = (10*p)%13
print(dp[5])
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            for k in range(1,10):
                if(tmp1[10-k]!=0):
                    tmp2*=(10**tmp1[10-k])
                    tmp2+=(10-k)*int("1"*tmp1[10-k])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
if(1 in A):
    if(4 in A):
        A.remove(4)
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
if(5 in A):
    if(3 in A):
        A.remove(3)
    if(2 in A):
        A.remove(2)
if(3 in A):
    if(2 in A):
        A.remove(2)
if(9 in A):
    if(6 in A):
        A.remove(6)
if(7 in A):
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])