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

def mergesort(a, left, right):
    if left + 1 < right:
        mid = int((left + right)/2)
        mergesort(a, left, mid)
        mergesort(a, mid, right)
        merge(a, left, mid, right)
    return a

def merge(a, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [a[left + i] for i in range(n1)]
    R = [a[mid + i] for i in range(n2)]
    L.append(1e10)
    R.append(1e10)
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

store_num, drink_num = [int(i) for i in input().split(" ")]
a_list = []
for i in range(store_num):
    a, b = [int(i) for i in input().split(" ")]
    for j in range(b):
        a_list.append(a)
b_list = mergesort(a_list, 0, len(a_list))
ans = 0
for i_ in range(drink_num):
    ans += b_list[i_]
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = []
for i in range(n):
    i,j = (map(int, input().split()))
    a += [[i,j]]
a = sorted(a)
count = 0
value = 0
for (i,j) in a:
    if count + j >= m:
        value += (m - count) * i
        break
    else:
        value += i * j
        count += j
print(value)
### BUGGY CODE ###

MOD = 1e9 + 7

n = int(input())
can = []
for _ in range(n):
    can.append([int(c) for c in input().split()])

dp = [0] * (2 ** n)
dp[0] = 1

for mask in range(2 ** n - 1):
    a = bin(mask).count('1')
    for b in range(n):
        if can[a][b] and not(mask & (1 << b)):
            m2 = mask ^ (1 << b)
            dp[m2] = dp[m2] + dp[mask]
            if dp[m2] > MOD:
                dp[m2] -= MOD


print(dp[(2**n) - 1])


### FIXED CODE ###

MOD = int(1e9 + 7)

n = int(input())
can = []
for _ in range(n):
    can.append([int(c) for c in input().split()])

dp = [0] * (2 ** n)
dp[0] = 1

for mask in range(2 ** n - 1):
    a = bin(mask).count('1')
    for b in range(n):
        if can[a][b] and not(mask & (1 << b)):
            m2 = mask ^ (1 << b)
            dp[m2] = dp[m2] + dp[mask]
            if dp[m2] > MOD:
                dp[m2] -= MOD


print(dp[(2**n) - 1])
### BUGGY CODE ###

s = input().rstrip().split(' ')
h = int(s[0])
n= int(s[1])

A = []
B = []

for i in range(n):
    AB = list(map(int, input().rstrip().split(' ')))
    A.append(AB[0])
    B.append(AB[1])

dp = [[float('inf')] * (h+1)] * (n+1)
dp[0][0] = 0

def min(a, b):
    if a < b:
        return a
    else:
        return b

for i in range(n):
    for j in range(h):
        dp[i+1][j] = dp[i][j]
        dp[i+1][min(j + A[i], h)] = min(dp[i + 1][min(j + A[i], h)], dp[i + 1][j] + B[i])

print(dp[n][h])


### FIXED CODE ###

s = input().rstrip().split(' ')
h = int(s[0])
n= int(s[1])

A = []
B = []

for i in range(n):
    AB = list(map(int, input().rstrip().split(' ')))
    A.append(AB[0])
    B.append(AB[1])

dp = [[float('inf')] * (h+1)] * (n+1)
dp[0][0] = 0

def min(a, b):
    if a < b:
        return a
    else:
        return b

for i in range(n):
    for j in range(h):
        dp[i+1][j] = dp[i][j]
        dp[i+1][min(j + A[i], h)] = min(dp[i + 1][min(j + A[i], h)], dp[i + 1][j] + B[i])

print(dp[n][h])
### BUGGY CODE ###

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

ans=0
for i in range(N-1):
    sum=0
    while H[i]>=H[i+1]:
        sum += 1
        i += 1
        if i==N-1:
            break
    ans = max(ans,sum)
print(ans)

### FIXED CODE ###

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

ans=0
sum=0
for i in range(N-1):
    if H[i]>=H[i+1]:
        sum += 1
    else:
        sum = 0
    ans = max(ans,sum)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
for i in range(Q):
  b,c = map(int, input().split())
  cnt = 0
  while b in A:
    A.remove(b)
    A.append(c)
    cnt += 1
  ans += (c-b) * cnt
  print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
C = Counter(A)

for i in range(Q):
  b, c = map(int, input().split())
  if C[b] != 0:
    cnt = C[b]
    C[c] += cnt
    C[b] = 0
    ans += (c-b) * cnt
  print(ans)
### BUGGY CODE ###

n=int(input())
sum=0
a=list(map(int, input().split()))
for i in range(n):
  for j in range(i+1, n):
    #print(i,j)
    sum+=a[i]*a[j]
  sum = sum%((10**9)+7)

print(sum)


### FIXED CODE ###

n=int(input())
sums=0
a=list(map(int, input().split()))
b = sum(a)
for i in range(n):
  b -= a[i]
  sums += a[i]*b
  sums = sums%((10**9)+7)
print(sums)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
i = 0

while i < q:
  l, r = map(int, input().split())
  print(s.count("AC", l-1, r))
  i += 1

### FIXED CODE ###

n, q = (int(i) for i in input().split())  
s = input()

count_list = []
bef_str = ''
bef_count = 0

for x in s:
  if bef_str == 'A' and x == 'C':
    bef_count += 1
    
  count_list.append(bef_count)
  bef_str = x
    
for i in range(q):
  l, r = (int(i) for i in input().split())
  print(count_list[r-1] - count_list[l-1])
### BUGGY CODE ###

from collections import deque

def main():
    n,x,y = map(int,input().split())
    cnt = [0]*(n)
    path = [(i, i+1) for i in range(n-1)]
    path.append((x-1, y-1))
    res = []
    for i in range(n):
        d = [float('inf')]*n
        que = deque([(i, 0)])
        while que:
            idx, c = que.popleft()
            if d[idx]!=float('inf'):
                continue
            else:
                d[idx] = min(d[idx], c)
                for s,g in path:
                    if s==idx:
                        que.append((g, c+1))
                    if g==idx:
                        que.append((s, c+1))
        res.append(d)
    for r in res:
        for i in range(n-1):
            cnt[i] += r.count(i)
    for c in cnt[1:]:
        print(c//2)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
cnt = [0]*n
for i in range(n):
    for j in range(i+1, n):
        cnt[g[i][j]] += 1
for c in cnt[1:]:
    print(c)
### BUGGY CODE ###

from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def f(rs, gs, bs):
    res = 0
    for i in rs:
        for j in reversed(gs):
            if not (i < j):
                break
            for k in reversed(bs):
                if not (j < k):
                    break
                if (j - i) != k - j:
                    res += 1
    return res
    # ir,ig,ib=(0,0,0)
    # while True:
    #     i= rs[ir]
    #     j= gs[ig]
    #     k= bs[ib]
    #     if i<j and j<k and (j-i)!=k-j:
    #         res+=1
    #


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

    rs = []
    gs = []
    bs = []

    for i, c in enumerate(S):
        if c == 'R':
            rs.append(i)
        elif c == 'G':
            gs.append(i)
        else:
            bs.append(i)
    print(f(rs, gs, bs) + f(rs, bs, gs) + f(gs, rs, bs) + f(gs, bs, rs) + f(bs, rs, gs) + f(bs, gs, rs))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def f(rs, gs, bs):
    res = 0
    lgs = len(gs)
    lbs = len(bs)
    for i in rs:
        j = bisect.bisect_left(gs, i)
        k = bisect.bisect_left(bs, i)
        res += (lgs - j) * (lbs - k)

        for jj in range(j, lgs):
            d = (gs[jj] - i)
            index = bisect.bisect_left(bs, i + 2 * d)
            if index != lbs:
                if bs[index] == i + 2 * d:
                    res -= 1

        for kk in range(k, lbs):
            d = (bs[kk] - i)
            index = bisect.bisect_left(gs, i + 2 * d)
            if index != lgs:
                if gs[index] == i + 2 * d:
                    res -= 1


        # for j in reversed(gs):
        #     if not (i < j):
        #         break
        #     for k in reversed(bs):
        #         if not (i < k):
        #             break
        #         if j < k:
        #             if (j - i) != k - j:
        #                 res += 1
        #         else:
        #             if (k - i) != j - k:
        #                 res += 1

    return res


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

    rs = []
    gs = []
    bs = []

    for i, c in enumerate(S):
        if c == 'R':
            rs.append(i)
        elif c == 'G':
            gs.append(i)
        else:
            bs.append(i)
    print(f(rs, gs, bs) + f(gs, rs, bs) + f(bs, rs, gs))


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

n,k = map(int,input().split())
a = list(map(int,input().split()))
p = 1;
for i in range(k):
	p *= a[i]
for i in range(k,n):
	r = p
	r /= a[i-k]
	r *= a[i]
	if r > p:
		print("Yes")
	else:
		print("No")
	p = r

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
p = 1
for i in range(k,n):
	if a[i] > a[i-k]:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

print(*ans, sep=" ")


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

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

h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


### FIXED CODE ###

h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])
### BUGGY CODE ###

import itertools

n, m = map(int, input().split())
a = list( map(int, input().split()))
anslist = []

for x, y in itertools.product(a, a):
    anslist.append(x+y)

anslist.sort(reverse=True)

ans = sum(anslist[:m])

print(ans)

### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate


n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

b = [0] + a
b.sort(reverse=True)
b = [0] +b
b = list(accumulate(b))

def isok(sum_):
    n_pattern = 0
    for i in range(n):
        n_pattern += n - bisect_left(a, sum_ - a[i])
        if n_pattern >= m:
            return True

    return False

ok = min(a)*2
ng = max(a)*2 +1

while ng - ok > 1:
    mid = (ok+ng)//2
    if isok(mid):
        ok = mid
    else:
        ng = mid

sum_ng = ng
sum_ok = ok

m_counter_ng = 0

ans = 0
for i in range(n):
    id_ng = bisect_left(a, sum_ng - a[i])
    ans += b[n-id_ng]
    ans += a[i]*(n - id_ng)
    m_counter_ng += n - id_ng

ans += sum_ok * (m - m_counter_ng)

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

from collections import Counter


def getinputdata():
    # 配列初期化
    array_result = []

    data = input()

    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            array_temp = []

            if (data != ""):

                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result


arr_data = getinputdata()

n = int(arr_data[0][0])

power = 1

for i in range(1, 1 + n):
    power *=  i

print(power % (10 **9 +7))


### FIXED CODE ###

import math
def getinputdata():

    array_result = []

    data = input()

    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if (data != ""):

                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])

power = 1

print(math.factorial(n) % (10 ** 9 + 7))
### BUGGY CODE ###

a, b, c, d = map(int, input().split())

cnt = 0
for i in range(a, b+1):
    cnt += 1 if (i % c) != 0 and (i % d) != 0 else 0

print(cnt)


### FIXED CODE ###

from fractions import gcd

a, b, c, d = map(int, input().split())


def f(n):
    x = n//c
    x += n//d
    lcm = c*d//gcd(c, d)
    x -= n//lcm
    return n-x


print(f(b)-f(a-1))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()

def primes_for(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

l = primes_for(max(A))
s = set()
for x in l:
    if x != 1:
        if x in s:
            print("setwise coprime")
            exit()
        else:
            s.add(x)
    cnt = 0
    for y in A:
        if y%x == 0:
            cnt += 1
    if cnt >= 2:
        print("setwise coprime")
        break
else:
    print("pairwise coprime")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")
### BUGGY CODE ###

from itertools import combinations

n = int(input())
l = [int(v) for v in input().split(' ')]

comb = combinations(l, 3)

sum = 0
for value in comb:
    if value[0] < value[1] + value[2] and value[1] < value[0] + value[2] and value[2] < value[0] + value[1]:
        sum += 1

print(sum)


### FIXED CODE ###

import bisect

n = int(input())
l = [int(v) for v in input().split(' ')]
sum = 0
l.sort()
for i in range(n):
    for j in range(n):
        if i < j:
            ab = l[i] + l[j]
            index = bisect.bisect_left(l, ab)
            sum += index - j - 1
print(sum)
### BUGGY CODE ###

w = str(input())
#print(len(w))
la = []
lz =[]
ans = []
for i in range(len(w)):
  if w[i] == 'A':
    la.append(i)
  elif w[i] == 'Z':
    lz.append(i)
for i in range(len(la)):
  for j in range(len(lz)):
    a = lz[j] - la[i] + 1
    ans.append(a)

print(max(ans))

### FIXED CODE ###

w = input()

print(w.rindex('Z')-w.index('A')+1)
### BUGGY CODE ###

from collections import deque

h, w = map(int,input().split())
alist = [input().strip() for i in range(h)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*w for i in range(h)]
q = deque()
for y, row in enumerate(alist):
  for x, c in enumerate(row):
    if c=='#':
      dp[y][x] = 0
      q.append((x,y))

while q:
  x, y = q.popleft()
  d = dp[y][x]
  for dx, dy in dxy:
    nx, ny = x+dx, y+dy
    if not 0 <= nx < w:
      continue
    if not 0 <= ny < h:
      continue
    if dp[ny][nx] <= d+1:
      continue
    dp[ny][nx] = d+1
    q.append((nx,ny))

print(max(max(row) for row in dp))


### FIXED CODE ###

from collections import deque

h, w = map(int,input().split())
alist = [input().strip() for i in range(h)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*w for i in range(h)]
q = deque()
for y, row in enumerate(alist):
  for x, c in enumerate(row):
    if c=='#':
      dp[y][x] = 0
      q.append((x,y))

while q:
  x, y = q.popleft()
  d = dp[y][x]
  for dx, dy in dxy:
    nx, ny = x+dx, y+dy
    if not 0 <= nx < w:
      continue
    if not 0 <= ny < h:
      continue
    if dp[ny][nx] <= d+1:
      continue
    dp[ny][nx] = d+1
    q.append((nx,ny))

print(max(max(row) for row in dp))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]
b = []
for i in range(n):
    b.append(a[i])
    b.reverse()
b_str = list(map(str, b))
print(" ".join(b_str))

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
a = [x for x in sys.stdin.readline().split()]
b = [a[i] for i in range(n) if i % 2 != 0]
rb = b[::-1]
c = [a[i] for i in range(n) if i % 2 == 0]
rc = c[::-1]

if n % 2 == 0:
    ans = rb + c
else:
    ans = rc + b

ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

def gcd(a,b):
    i = 2
    temp = 1
    while(i <= b):
        while(a % i == 0 and b % i == 0):
            temp = temp * i
            a = a / i
            b = b / i
        i = i + 1
    print temp

l = raw_input().split()
if(int(l[0]) > int(l[1])):
    gcd(int(l[0]),int(l[1]))
else:
    gcd(int(l[1]),int(l[0]))


### FIXED CODE ###

def gcd(a,b):
    if(b):
        return gcd(b,a%b)
    return a

l = raw_input().split()
if(int(l[0]) > int(l[1])):
    print gcd(int(l[0]),int(l[1]))
else:
    print gcd(int(l[1]),int(l[0]))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []
A = [int(input()) for i in range(Q)]

for i in range(N):
    P = K - Q + A.count(i+1)
    if P > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
p = [0] * N 
for i in A:
    p[i-1] += 1    

for i in range(N):
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#C_Repsept
import math
K = int(input())
X = 0
kekka = -1
total = -1
if K % 2 == 1:
    for i in range(K): 
        X = X + pow(10,i) * 7
        kekka = X % K
        if kekka == 0:
            total = i+1
            break
# 出力
print(total)

### FIXED CODE ###

#C_Repsept
K = int(input())
if K % 7 == 0 :
    L = int( 9 * K / 7 )
else:
    L = 9 * K
X = 0
kekka = 1
total = -1
if L % 2 == 1:
    if L % 5 != 0:
        for i in range(L): 
            kekka = kekka * 10 % L
            if kekka == 1:
                total = i+1
                break
# 出力
print(total)
### BUGGY CODE ###

import sys

def get(x,n):
    return ((1<<x)&(n))!=0


def main():
    mod=1000000000+7
    n=int(sys.stdin.readline())
    a=list(map(int,sys.stdin.readline().split()))
    ans=0
    for x in range(60):
        now=get(x,a[-1])
        nnow=not get(x,a[-1])
        for i in range(n-2,-1,-1):
            now+=get(x,a[i])
            nnow+=not get(x,a[i])
            if get(x,a[i]):
                ans+=(2**x)*nnow
            else:
                ans+=(2**x)*now
    print(ans%mod)
main()


### FIXED CODE ###

import sys

def get(x,n):
    return ((1<<x)&(n))!=0


def main():
    mod=1000000000+7
    n=int(sys.stdin.readline())
    a=list(map(int,sys.stdin.readline().split()))
    ans=0
    cur=1
    for x in range(60):
        res=get(x,a[-1])
        now=res
        nnow=not res
        total=0
        for i in range(n-2,-1,-1):
            res=get(x,a[i])
            now+=res
            nnow+=not res
            if res:
                total+=nnow
            else:
                total+=now
        ans+=cur*total
        ans%=mod
        cur*=2
    print(ans%mod)
main()
### BUGGY CODE ###

import numpy as np

MOD = 998244353
N, K = list(map(int, input().split()))

dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

def shift_and_add(dp, mv, m, i):
    dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*m))
    dp %= MOD
        
dp[1] = 1
for i in range(1, N+1):
    m = dp[i]
    shift_and_add(dp, mv, m, i)

print(dp[N])


### FIXED CODE ###

MOD = 998244353
N, K = list(map(int, input().split()))

a = [0] * (N+1)
f = [0] * (N+1)
mv = list()
for i in range(K):
    mv.append(list(map(int, input().split())))

def solve(N, a, f):
    for i in range(1, N+1):
        f[i] = (f[i-1] + a[i]) % MOD
        for j in range(len(mv)):
            l, r = mv[j]
            if i+l < N+1: a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N+1: a[i+r+1] = (a[i+r+1] - f[i]) % MOD

a[1] = 1
mv.sort()
solve(N, a, f)

print(a[N])
### BUGGY CODE ###

s=input()
n=int(input())
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if f==1:
            s=c+s
        else:
            s=s+c
    else:
        s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
cnt=0
l=[]
r=[]
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            l.append(c)
        else:
            r.append(c)
    else:
        cnt+=1
if cnt%2==0:
    print(''.join(l[::-1])+s+''.join(r))
else:
    print(''.join(r[::-1])+s[::-1]+''.join(l))
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0

for p in range(1000):
    p = str(p).zfill(3)
    i = 0
    for j in range(N):
        if p[i] == S[j]:
            i += 1
        if i == 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = list(input())
    ans = 0

    for p in range(1000):
        p = str(p).zfill(3)
        i = 0
        for j in range(N):
            if p[i] == S[j]:
                i += 1
            if i == 3:
                ans += 1
                break

    print(ans)


if __name__ == "__main__":
    main()