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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

#nCr
def comb(n,r):
    x = 1
    y = 1
    for i in range(r):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

ans = 0
for i in range(n):
    c = comb(n-i-1,k-1)
    ans += A[n-1-i] * c - A[i] * c
    ans %= mod

print(ans)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

f=[1]
for i in range(1,n+1):
  f.append(f[-1]*i % mod)

#nCr
def comb(n,r):
    if n <= 0 or r <= 0:
        return 0
    x = f[n] % mod
    y = f[r] * f[n-r] % mod
    return (x * pow(y, mod-2, mod) % mod)

ans = 0
for i in range(n):
    c = comb(n-i-1,k-1)
    ans += A[n-1-i] * c - A[i] * c
    ans %= mod
    if c == 1:
        break

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

N=int(input())

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
  
cost=[list(map(int, input().split())) for i in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    if i<j:
      d=dijkstra(i,N,cost)
      if d[j]!=cost[i][j]:
        print(-1)
        exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

### FIXED CODE ###

N=int(input())
import copy
def warshall_floyd(N):
  d=[list(map(int,input().split())) for i in range(N)]
  D=copy.deepcopy(d)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  if d==D:
    return d
  else:
    return -1
  
E=warshall_floyd(N)
if E==-1:
  print(-1)
  exit()
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)
### BUGGY CODE ###

value = list(input())
res = 0
while True:
    if len(value) == 1 or len(value) == 0:
        break
    elif value[0] != value[-1] and value[0] != "x" and value[-1] != "x":
        res = -1
        break
    elif value[0] == value[-1]:
        value.pop(0)
        value.pop()
    else:
        value.extend("x") if value[0] == "x" else value.insert(0, "x")
        value.pop(0)
        value.pop()
        res += 1
print(res)


### FIXED CODE ###

s = input()
ns = s.replace('x', '')
if s == s[::-1]:
    print(0)
elif ns != ns[::-1]:
    print(-1)
else:
    cnt = 0
    i = 0
    j = len(s)-1
    while(i<j):
        if s[i]=='x' and s[j]!='x':
            cnt += 1
            j += 1
        elif s[i]!='x' and s[j]=='x':
            cnt += 1
            i -= 1
        i += 1
        j -= 1
    print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, K = map(int, input().split())
lst_0=list(map(int,input().split()))
DP=[float("INF")]*H
DP[0]=0
for i in range(1,H):
    for j in range(1,K+1):
        if i - j >= 0:
            DP[i]=min(DP[i],abs(lst_0[i]-lst_0[i-j])+DP[i-j])
print(DP[H-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, K = map(int, input().split())
lst_0=list(map(int,input().split()))
DP=[float("INF")]*H
DP[0]=0
for i in range(1,H):
    for j in range(1,K+1):
        if i - j >= 0:
            DP[i]=min(DP[i],abs(lst_0[i]-lst_0[i-j])+DP[i-j])
print(DP[H-1])
### BUGGY CODE ###

from itertools import permutations
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = c
    dp[b - 1][a - 1] = c

warshallFloyd()
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += dp[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(ans)

### FIXED CODE ###

from itertools import permutations
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = c
    dp[b - 1][a - 1] = c

warshallFloyd()
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += dp[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

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

q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * ((m + 1) * (n + 1))
    for i in range(1, m + 1):
        tmp = x[i - 1]
        for j in range(1, n + 1):
            if tmp == y[j - 1]:
                c[i * (n + 1) + j] = c[(i - 1) * (n + 1) + j - 1] + 1
            elif c[(i - 1) * (n + 1) + j] >= c[i * (n + 1) + j - 1]:
                c[i * (n + 1) + j] = c[(i - 1) * (n + 1) + j]
            else:
                c[i * (n + 1) + j] = c[i * (n + 1) + j - 1]
    print(c[m * (n + 1) + n])


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    return c[-1]


q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    ans.append(lcs(x, y))

print(*ans, sep="\n")
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    p.sort(key=lambda x:sum(x),reverse=True)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
      else:
        l = y
    ans = min(ans,t_a)

  print(ans)
  
main()

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked=[]
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            checked.append(pair)
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if [pair[0]+x,pair[1]+y] not in checked and s[pair[0]+x][pair[1]+y]==".":
                    stack_.append([pair[0]+x,pair[1]+y])
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

### FIXED CODE ###

h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked = [[False]*(w+2) for _ in range(h+2)]
        checked[i][j]=True
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if s[pair[0]+x][pair[1]+y]=="." and checked[pair[0]+x][pair[1]+y] == False:
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked[pair[0]+x][pair[1]+y] = True
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)
### BUGGY CODE ###

K, S = list(map(int, input().split()))
re = 0
for x in range(K+1):
    for y in range(K+1):
        z = min(K, max(0, S-x-y))
        if x + y + z == S:
            re += 1
print(re)

### FIXED CODE ###

K, S = list(map(int, input().split()))
re = 0
for x in range(min(S+1, K+1)):
    for y in range(min(S+1-x, K+1)):
        if S - x - y <= K:
            re += 1
print(re)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [{} for _ in range(N)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if l in dp[i]:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print(search(0, 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if dp[i][l] != -1:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print(search(0, 0))
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    for j in range(i+1,N+1):
        if sum(A[i:j])==0:
            ans+=1
            
print(ans)

### FIXED CODE ###

from collections import defaultdict

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

C = defaultdict(int)

ans = 0
sumA = 0
for a in A:
    sumA += a
    C[sumA] += 1
    if C[sumA] >=2:
        ans += C[sumA]-1
        
for i in range(1,C[0]+1): ans+= 1
    
print(ans)
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections

# n = int(input())
R, G, B, N = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

max_r, max_g, max_b = N // R, N // G, N // B
ans = []

r, g, b = 0, 0, 0
cnt = 0
for r in range(3000):
    if R * r > N:
        break

    max_g = (N - R * r) // G

    for g in range(max_g + 1):
        if R * r + G * g > N:
            break
        x = (N - (R * r + G * g))
        if x % B == 0 and x >= 0:
            b = x // B
            a = (r, g, b)
            cnt += 1
            # ans.append(a)

# print(len(ans))
print(cnt)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections

# n = int(input())
R, G, B, N = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

# max_r, max_g, max_b = N // R, N // G, N // B
ans = []

r, g, b = 0, 0, 0
cnt = 0

max_r = N // R
for r in range(max_r + 1):
    if R * r > N:
        break

    max_g = (N - R * r) // G

    for g in range(max_g + 1):
        if R * r + G * g > N:
            break
        x = (N - (R * r + G * g))
        if x % B == 0 and x >= 0:
            # b = x // B
            # a = (r, g, b)
            cnt += 1
            # ans.append(a)

# print(len(ans))
print(cnt)
### BUGGY CODE ###

dic = []

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic.append(arg)
  else:
    if arg in dic:
      print("yes")
    else:
      print("no")

### FIXED CODE ###

dic = {}

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic[arg] = 0
  else:
    if arg in dic:
      print("yes")
    else:
      print("no")
### BUGGY CODE ###

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

for i in range(1, N+1):
	print(A.count(i))

### FIXED CODE ###

import collections

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

for i in range(1, N+1):
	print(c[i])
### BUGGY CODE ###

from sys import stdin
import bisect


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

li = [7,5,3]
point = 0
for i in range(n+1):
    s = str(i)
    if s.count("7") > 0 and s.count("5") > 0 and s.count("3") > 0 and s.count("0") == 0 and  s.count("1") == 0 and s.count("2") == 0 and s.count("4") == 0 and s.count("6") == 0 and s.count("8") == 0 and s.count("9") == 0:
        point += 1
print(point)

### FIXED CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**6) 
import bisect

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

li = [7,5,3]

if n < 357:
    print(0)
    exit()

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

kazu = 0
point = 0
k = "0"
while int(k) <= n:
    k = Base_10_to_n(kazu,4)
    k = k.replace("3","7").replace("1","3").replace("2","5")
    if all(k.count(c)>0 for c in "753")and k.count("0") == 0:
        if int(k) <= n:
            point += 1
    kazu += 1
print(point)
### BUGGY CODE ###

from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[True]*w for _ in range(h)]

ans = 0
while True:
    ns = deque()
    for i, j in s:
        a[i][j] = False

        if i>0 and a[i-1][j]:
            ns.append((i-1, j))
        if i<h-1 and a[i+1][j]:
            ns.append((i+1, j))
        if j>0 and a[i][j-1]:
            ns.append((i, j-1))
        if j<w-1 and a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

import sys
readline = sys.stdin.readline

# Sのそれぞれの項目について
# (1)Tに属さない
# (2)Tに属すが計算に使われない
# (3)Tに属して計算に使われる
# の3通りがある

# dp[i][j] = i番目の数を処理したときに、合計がjになるものは何通りあるか

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

dp = [[0] * (S + 1) for i in range(N + 1)]

dp[0][0] = 1
for i in range(N):
  val = A[i]
  for j in range(len(dp[i]) - 1, -1, -1):
    if dp[i][j] == 0:
      continue
    dp[i + 1][j] += dp[i][j] * 2 # 使わない場合、選ばない場合
    dp[i + 1][j] %= DIV
    if j + val <= S:
      dp[i + 1][j + val] += dp[i][j]
      dp[i + 1][j + val] %= DIV
  
print(dp[-1][-1])

### FIXED CODE ###

# 解説AC
# Tの部分集合をUとすると
# A[i]番目の項目について、
# (1)Tに選ばれない
# (2)Uに選ばれない
# (3)Uに選ばれる
# の3通りの遷移がある
# (1)(2)の場合も含めて数え上げていく（その場合、和は変わらない）

import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

dp = [0] * (S + 1)
dp[0] = 1
for i in range(N):
  newline = [0] * (S + 1)
  for j in range(len(dp)):
    # 選択肢(1)(2)の場合
    newline[j] += dp[j] * 2
    newline[j] %= DIV
    # 選択肢(3)の場合
    if j + A[i] <= S:
      newline[j + A[i]] += dp[j]
      newline[j + A[i]] %= DIV
  dp = newline

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

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

### FIXED CODE ###

from collections import Counter 
n=int(input())
a=Counter([int(input()) for _ in range(n)])
ans=0
for i in a.values():
  ans+=i%2
print(ans)
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=np.zeros(N)
B=np.zeros([M,2])
for i in range(M):
  k,l=map(int,input().split())
  B[i,0]=k
  B[i,1]=l

C={1}
D=set()
E=[]
while B.shape[0]>0:
  for i in range(B.shape[0]):
    if B[i,0] in C:
      if A[int(B[i,1])-1]==0:
        A[int(B[i,1])-1]=B[i,0]
        D.add(B[i,1])
      E.append(i)
    elif B[i,1] in C:
      if A[int(B[i,0])-1]==0:
        A[int(B[i,0])-1]=B[i,1]
        D.add(B[i,0])
      E.append(i)
  B=np.delete(B,E,0)
  E=[]
  C=D
  D=set()

print("Yes")
for i in range(1,N):
  print(int(A[i]))

### FIXED CODE ###

import queue
N,M=map(int,input().split())
ans=[0] * N
q=queue.Queue()
q.put(1)

import sys
s = sys.stdin.readlines()
G=[[] for _ in range(N)]

for e in s:
  a, b = map(int, e.split())
  G[a-1].append(b)
  G[b-1].append(a)
  
c=0

while c!=N-1:
  r=q.get()
  for i in G[r-1]:
    if ans[i-1]==0 and i!=1:
      ans[i-1]=r
      q.put(i)
      c+=1

print("Yes")
for i in range(N-1):
  print(ans[i+1])
### BUGGY CODE ###

N=int(input())
S=input()
count=0
for i in range(1000):
    p=str(int(i/100))+str(int(i/10%10))+str(int(i%10))
    l=0
    for j in range(N):
        if S[j]==p[l]:
            l+=1
        if l==3:
            count+=1
            break
print(count)

### FIXED CODE ###

N=int(input())
S=input()
count=0
for i in range(1000):
    p='0'*(3-len(str(i)))+str(i)
    p1=S.find(p[0])
    if p1!=-1:
        p2=S[p1+1:].find(p[1])
        if p2!=-1:
            p3=S[p1+p2+2:].find(p[2])
            if p3!=-1:
                count+=1
print(count)
### BUGGY CODE ###

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            x1 = xy[i][0]
            y1 = xy[i][1]
            x2 = xy[j][0]
            y2 = xy[j][1]
            pq.append((x2 - x1, y2 - y1))

ans = N
for p,q in pq:
    tmp = 0
    for i in range(N):
        for j in range(N):
            if i != j:
                x1 = xy[i][0]
                y1 = xy[i][1]
                x2 = xy[j][0]
                y2 = xy[j][1]
                if x2 - x1 == p and y2 - y1 == q:
                    tmp += 1
    ans = min(ans, N - tmp)

print(ans)


### FIXED CODE ###

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            x1 = xy[i][0]
            y1 = xy[i][1]
            x2 = xy[j][0]
            y2 = xy[j][1]
            pq.append((x2 - x1, y2 - y1))

ans = N
for p,q in pq:
    tmp = 0
    for i in range(N):
        for j in range(N):
            if i != j:
                x1 = xy[i][0]
                y1 = xy[i][1]
                x2 = xy[j][0]
                y2 = xy[j][1]
                if x2 - x1 == p and y2 - y1 == q:
                    tmp += 1
    ans = min(ans, N - tmp)

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

all_num, select_num = map(int, input().split())
dice = [int(a) for a in input().split()]
max_sum = 0

for i in range(all_num - (select_num - 1)):
    if i == 0 or dice[i + select_num -1] > dice[i - 1]:
        this_sum = sum(dice[i:(i + select_num)])
        if this_sum > max_sum:
            max_sum = this_sum
    else:
        pass

print((max_sum + select_num) * 0.5)

### FIXED CODE ###

all_num, select_num = map(int, input().split())
dice = [int(a) for a in input().split()]

for i in range(all_num - (select_num - 1)):
    if i == 0:
        max_sum = this_sum = sum(dice[i:(i + select_num)])
    else:
        this_sum = this_sum - dice[i - 1] + dice[i + select_num - 1]

        if this_sum > max_sum:
            max_sum = this_sum

print((max_sum + select_num) * 0.5)
### BUGGY CODE ###

n = int(input())
from math import sqrt
root = int(sqrt(n))

for i in range(root,n+1):
    if n%i == 0:
        ans = i+(n/i)-2
        break
print(int(ans))


### FIXED CODE ###

n = int(input())
from math import sqrt
root = int(sqrt(n))

for i in range(root,0,-1):
    if n%i == 0:
        ans = i+(n/i)-2
        break
print(int(ans))