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

#!/usr/bin/env python3
import sys
INF = float("inf")
import bisect
from collections import Counter
from collections import defaultdict
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


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

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

# AtCoder Beginner Contest
# Problem B

if __name__ == '__main__':
    a, b, k = list(map(int, input().split()))

    if (b - a + 1) <= 2 * k:
        for i in range(a, b + 1):
            print(i)
    else:
        for j in range(a, b + 1):
            if (j <= a + k - 1) or (j > b - k):
                print(j)


### FIXED CODE ###

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

# AtCoder Beginner Contest
# Problem B

if __name__ == '__main__':
    a, b, k = list(map(int, input().split()))

    if (b - a + 1) <= 2 * k:
        for i in range(a, b + 1):
            print(i)
    else:
        for j in range(a, a + k):
            print(j)
        for j in range(b - k + 1, b + 1):
            print(j)
### BUGGY CODE ###

from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
ln = [i for i in a if a.count(i) >= 2]
y = [min(a)]
while a:
    v = a.popleft()
    x = 0
    for j in y:
        if v % j == 0:
            break
        else:
            x += 1
        if x == len(y):
            y.append(v)
u = [i for i in y if i not in ln]
print(len(u))

### FIXED CODE ###

from collections import Counter
import bisect
n = int(input()) #リストの要素数
a = list(map(int, input().split())) #リストの要素
cnt = Counter(a) #aの要素数についての辞書
a.sort()#aを小さい順にソート
ans = 0
mx = 10 ** 6
p = [0] * (mx + 1)
for i in a:
    if p[i] == 0:
        for j in range(mx + 1):
            x = i * j
            if x > mx:
                break
            p[x] = 1 #pの中でaの要素iの倍数として表現できるものに１
        if cnt[i] == 1:
            ans += 1 #pの中で任意のiの倍数として表現できず、かつ１つのみ存在するものをカウント
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
dic = {}
s = sum(a)
for i in range(1,10**5+1):
    if i in a:
        dic[i] = a.count(i)
    else:
        dic[i] = 0
for j in range(q):
    b,c = map(int,input().split())
    s += (c-b)*dic[b]
    dic[c] += dic[b]
    dic[b] = 0
    print(s)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
num = Counter(a)
s = sum(a)
for _ in range(q):
    b,c = map(int,input().split())
    s += (c-b)*num[b]
    num[c] += num[b]
    num[b] = 0
    print(s)
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7
    dp = [[0 for _ in range(13)] for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if s[i - 1] == "?":
            for now in range(10):
                for before in range(13):
                    ind = (now + 10 * before) % 13
                    dp[i][ind] += dp[i - 1][before]
                    dp[i][ind] %= mod
        else:
            for before in range(13):
                ind = (int(s[i - 1]) + 10 * before) % 13
                dp[i][ind] += dp[i - 1][before]
                dp[i][ind] %= mod
    print(dp[n][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7
    dp = [[0 for _ in range(13)] for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if s[i - 1] == "?":
            for now in range(10):
                for before in range(13):
                    ind = (now + 10 * before) % 13
                    dp[i][ind] += dp[i - 1][before]
                    dp[i][ind] %= mod
        else:
            for before in range(13):
                ind = (int(s[i - 1]) + 10 * before) % 13
                dp[i][ind] += dp[i - 1][before]
                dp[i][ind] %= mod
    print(dp[n][5])


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

def cf(a, b):
    cf = [1]
    for i in range(2, min(a, b)+1):
        if a % i == 0 and b % i == 0:
            if (i == 2) or (i > 2 and i % 2 != 0):
                cf.append(i)
            else:
                pass
    return cf

A, B = map(int, input().split())
cf_l = cf(A, B)

for i in range(1, len(cf_l)):
    for j in range(i+1, len(cf_l)):
        if cf_l[j] % cf_l[i] == 0:
            cf_l.pop(j)

print(len(cf_l))


### FIXED CODE ###

def prime_factorize(n):
    pf = []
    while n % 2 == 0:
        pf.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            pf.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        pf.append(n)
    return pf

A, B = map(int, input().split())

prime_A = set(prime_factorize(A))
prime_B = set(prime_factorize(B))
ans = len(prime_A & prime_B) + 1

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

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

### FIXED CODE ###

N=int(input())
As=list(map(int, input().split()))
man = [""] * N
for i in range(N):
  man[As[i]-1] = str(i+1)
result = ' '.join(man)
print(result)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = sorted(enumerate(arr), key=lambda tpl: -tpl[1])

dp = defaultdict(int)

def cal(ln, rn):
  if ln < 0 or rn < 0 or ln == rn == 0:
    return 0

  if dp[ln, rn] == 0:
    p, a = arr[ln + rn - 1]
    val_l = cal(ln - 1, rn) + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = cal(ln, rn - 1) + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  return dp[ln, rn]


print(max([cal(i, n - i) for i in range(n + 1)]))


### FIXED CODE ###


def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()
### BUGGY CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = ns()
        x -= 1
        y -= 1
        e[x].append(y)
        e[y].append(x)

    # dp[i][0]:i番目のノードが白のときの組み合わせの数
    # dp[i][1]:i番目のノードが黒のときの組み合わせの数
    dp = [[1, 1] for _ in range(n)]
    visited = [False for _ in range(n)]

    def dfs(vi, prnt):
        # if visited[vi]:
        #     return
        visited[vi] = True

        for chld in e[vi]:
            if chld == prnt or visited[chld]:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= (dp[chld][0] + dp[chld][1]) % MOD
            dp[vi][0] %= MOD
            # 親が黒田と子は白じゃないとダメ
            dp[vi][1] *= dp[chld][0]
            dp[vi][1] %= MOD

    dfs(0, -1)
    print((dp[0][0] + dp[0][1]) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    n = int(inp())
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        e[x].append(y)
        e[y].append(x)

    # dp[i][0]:i番目のノードが白のときの組み合わせの数
    # dp[i][1]:i番目のノードが黒のときの組み合わせの数
    dp = [[1, 1] for _ in range(n)]
    visited = [False for _ in range(n)]

    def dfs(vi, prnt):
        # if visited[vi]:
        #     return
        visited[vi] = True

        for chld in e[vi]:
            if chld == prnt or visited[chld]:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= (dp[chld][0] + dp[chld][1]) % MOD
            dp[vi][0] %= MOD
            # 親が黒田と子は白じゃないとダメ
            dp[vi][1] *= dp[chld][0] % MOD
            dp[vi][1] %= MOD

    dfs(0, -1)
    print((dp[0][0] + dp[0][1]) % MOD)


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

# -*- coding: utf-8 -*-
# 標準入力の取得
X = int(input())

# 求解処理


def get_B(A: int):
    return - 1 * (X - A ** 5) ** (1 / 5)


def main():
    A = 0
    while True:
        B = get_B(A)
        if (B.imag == 0) and (B.is_integer()):
            break
        A += 1

    result = f"{int(A)} {int(B)}"

    # 結果出力
    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力の取得
X = int(input())

# 求解処理


def get_value(A: int, B: int) -> int:
    return A**5 - B**5


A_min, A_max = -118, 119
B_min, B_max = -119, 118
result = ""
for A, B in itertools.product(range(A_min, A_max+1), range(B_min, B_max+1)):
    value = get_value(A, B)
    if value == X:
        result = f"{A} {B}"
        break

# 結果出力
print(result)
### BUGGY CODE ###

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

dp = [0] * n
for i in range(n - 1):
    for j in range(n):
        if graph[j] is not None:
            for k in graph[j]:
                dp[j] = max(dp[j], dp[k] + 1)
print(max(dp))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)

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

dp = [-1] * n
def count(a):
    if dp[a] != -1:
        return dp[a]
    else:
        dp[a] = 0
        for i in graph[a]:
            dp[a] = max(count(i) + 1, dp[a])
        return dp[a]

print(max([count(i) for i in range(n)]))
### BUGGY CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))
l = [] * total

tar2 = 0
calc_before = 0
calc_now = 0
for i in range(total+1-tar):
  calc_now = sum(dice_array[i:i+tar])
  if calc_before < calc_now:
    tar2 = i
    calc_before = calc_now
  calc_now = 0

sum = 0
for i in range(tar2, tar+tar2):
  cnt = 0
  for j in range(1, dice_array[i]+1):
    cnt += j
  sum += (cnt / dice_array[i])
  
print(sum)


### FIXED CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))

hope_array = [0.0] * total
for i in range(total):
   hope_array[i] = (dice_array[i] * (dice_array[i] + 1)) / 2 / dice_array[i]

dice_total = [0]
 
for i in range(total):
  dice_total.append(hope_array[i] + dice_total[i])
 
ans = dice_total[tar]
tar_num = tar
for i in range(total - tar):
  tmp = dice_total[i + 1 + tar] - dice_total[i + 1]
  if ans < tmp:
    ans = tmp

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

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

b = 0
for i in range(N):
    if S[N-i-1] == '#':
        b += (2**i)

print(min(bin((2**i-1)^b).count("1") for i in range(N+1)))

### FIXED CODE ###

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

w = [0] * N
b = [0] * N

if S[0] == '#':
    w[0] = 1
for i in range(1, N):
    if S[i] == '#':
        w[i] = w[i-1] + 1
    else:
        w[i] = w[i-1]

if S[N-1] == '.':
    b[N-1] = 1
for i in range(N-2, -1, -1):
    if S[i] == '.':
        b[i] = b[i+1] + 1
    else:
        b[i] = b[i+1]

m = min(b[0], w[N-1])
for n in range(N-1):
    v = w[n] + b[n+1]
    if v < m:
        m = v
print(m)
### BUGGY CODE ###

import heapq

INF = float('inf')

class Edge():
    def __init__(self, a, b, cost):
        self.a = a
        self.b = b
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.a, self.b, self.cost)

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 e in G[v]:
            if dist[e.b] > dist[v] + e.cost:
                dist[e.b] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.b], e.b))
    return dist

n, x, y = map(int, input().split())

g = [[] for i in range(n)]

for i in range(n-1):
    g[i].append(Edge(i, i+1, 1))
    g[i+1].append(Edge(i+1, i, 1))

g[x-1].append(Edge(x-1, y-1, 1))
g[y-1].append(Edge(y-1, x-1, 1))

ans = [0] * n

for i in range(n):
    for d in dijkstra(n, g, i):
        ans[d] += 1

for item in ans[1:]:
    print(item // 2)



### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for i in range(n)]
x -= 1
y -= 1
for i in range(n):
    for j in range(i+1, n):
        cand1 = j - i
        cand2 = abs(x - i) + 1 + abs(y-j)
        ans[min(cand1, cand2)] += 1

for item in ans[1:]:
    print(item)
### BUGGY CODE ###

S = list(input())
Q = int(input())
for i in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        S.reverse()
    elif Query[1] == "1":
        S.insert(0, Query[2])
    else:
        S.append(Query[2])
print("".join(S))


### FIXED CODE ###

import collections
S = input()
Q = int(input())
q = collections.deque()
q.append(S)
inversion = True
for i in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        inversion = not(inversion)
    elif Query[1] == "1":
        if inversion:
            q.appendleft(Query[2])
        else:
            q.append(Query[2])
    else:
        if inversion:
            q.append(Query[2])
        else:
            q.appendleft(Query[2])

if inversion:
    print("".join(q))
else:
    print("".join(q)[::-1])
### BUGGY CODE ###

import collections
def main():
  N=int(input())
  str_list = [input() for _ in range(N)]
  c = collections.Counter(str_list)
  d=sorted(c.items(), key=lambda x:x[0], reverse=False)
  for i in range(len(d)):
    if(d[i][1]==max(c.values())):
      print(d[i][0])
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
  n=int(input())
  arr=[input() for _ in range(n)]
  dic={}
  for i in range(n): #各単語の出現回数を数える
    if arr[i] not in dic:
      dic[arr[i]]=1
    else:
      dic[arr[i]]+=1
  largest=max(dic.values()) #最大の出現回数を求める
  ans=[]
  for keys in dic.keys():
    if dic[keys]==largest: #出現回数が最も多い単語を集計する
      ans.append(keys)
  ans=sorted(ans) #単語を辞書順に並べ替えて出力する
  for words in ans:
    print(words)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))
### BUGGY CODE ###

# coding: utf-8
from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "#" and visited[nx][ny] == INF:
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist

ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x, y))
print(ans)

### FIXED CODE ###

# coding: utf-8
from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "#" and visited[nx][ny] == INF:
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for i in range(H):
    for j in range(W):
        x, y = i, j
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x, y))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
flag =0
for i  in a:
    ans = ans*i
if ans >10**18:
 	print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
flag =0
for i  in a:
    if i == 0:
        flag=2
        break
if flag!= 2:
    for i  in a:
        ans = ans*i
        if ans > 10 ** 18:
            flag=1
            break


if flag==1:
    print(-1)
elif flag ==2:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
alist=list(map(int,input().split()))

posilist=[]
negalist=[]
zeronum=0

for a in alist:
    if a == 0:
        zeronum+=1
    elif a > 0:
        posilist.append(a)
    else:
        negalist.append(-a)
posilist.sort()
negalist.sort()

posinum=len(posilist)
neganum=len(negalist)

def shakutori(x,alist,blist,flag):
    sum=0
    alen=len(alist)
    blen=len(blist)

    a=0
    b=blen-1

    while a <= alen-1 and b >= 0:
        if flag and a == b:
            return sum
        if alist[a]*blist[b] <= x:
            if flag:
            	sum+= (b+1)-(a+1)
            else:
            	sum+= (b+1)
            a += 1
        else:
            b -=1
    return sum

if k <= posinum*neganum:
    k=posinum*neganum+1-k
    pnflag=False
elif k > n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2:
    k=k-(n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2)
    pnflag=True
else:
    print(0)
    sys.exit()

llim=0
ulim=10**19+1


while True:
    mid=(llim+ulim)//2
    if pnflag:
        d1=shakutori(mid,posilist,posilist,True)+shakutori(mid,negalist,negalist,True)
        d2=shakutori(mid+1,posilist,posilist,True)+shakutori(mid+1,negalist,negalist,True)
    else:
        d1=shakutori(mid,posilist,negalist,False)
        d2=shakutori(mid+1,posilist,negalist,False)
    if d1 < k <= d2:
        if pnflag:
            print(mid+1)
        else:
            print(-(mid+1))
        sys.exit()
    elif k <= d1:
        ulim = mid
    else:
        llim = mid



### FIXED CODE ###

import sys
n,k=map(int,input().split())
alist=list(map(int,input().split()))

posilist=[]
negalist=[]
zeronum=0

for a in alist:
    if a == 0:
        zeronum+=1
    elif a > 0:
        posilist.append(a)
    else:
        negalist.append(-a)
posilist.sort()
negalist.sort()

posinum=len(posilist)
neganum=len(negalist)

def shakutori(x,alist,blist,flag):
    sum=0
    alen=len(alist)
    blen=len(blist)

    a=0
    b=blen-1

    while a <= alen-1 and b >= 0:
        if flag and a == b:
            return sum
        if alist[a]*blist[b] <= x:
            if flag:
            	sum+= (b+1)-(a+1)
            else:
            	sum+= (b+1)
            a += 1
        else:
            b -=1
    return sum

if k <= posinum*neganum:
    k=posinum*neganum+1-k
    pnflag=False
elif k > n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2:
    k=k-(n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2)
    pnflag=True
else:
    print(0)
    sys.exit()

llim=0
ulim=10**19+1


while True:
    mid=(llim+ulim)//2
    if pnflag:
        d1=shakutori(mid,posilist,posilist,True)+shakutori(mid,negalist,negalist,True)
        d2=shakutori(mid+1,posilist,posilist,True)+shakutori(mid+1,negalist,negalist,True)
    else:
        d1=shakutori(mid,posilist,negalist,False)
        d2=shakutori(mid+1,posilist,negalist,False)
    if d1 < k <= d2:
        if pnflag:
            print(mid+1)
        else:
            print(-(mid+1))
        sys.exit()
    elif k <= d1:
        ulim = mid
    else:
        llim = mid
### BUGGY CODE ###

n = int(input())
s = input()
code = [[n,n,n] for i in range(1000)]

for i in range(n):
    si = int(s[i])
    for j in range(100):
        if code[j*10+si][1] < i and code[j*10+si][2] == n:
            code[j*10+si][2] = i
            #print(i,j*10+si,2)
        if code[si*100+j][0] == n:
            code[si*100+j][0] = i
            #print(i,si*100+j,0)
        if code[(j//10)*100+si*10+j%10][0] < i and code[(j//10)*100+si*10+j%10][1] == n:
            code[(j//10)*100+si*10+j%10][1] = i
            #print(i,(j//10)*100+si*10+j%10,1)

ans = 0
for i in range(1000):
    if code[i][2] < n:
        ans += 1

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/sumitrust2019/submissions/13016562を見た

n = int(input())
s = input()
ans = 0

pin = [str(i).zfill(3) for i in range(1000)]

for i in pin:
    idx = -1
    for j in i:
        idx = s.find(j,idx+1)
        if idx < 0:
            break
    else:
        ans += 1

print(ans)