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

S = input()
N = len(S)
MOD = 10 ** 9 + 7

q = 3 if S[0] == '?' else 1
a = b = c = 0
def fq(a, b, c, q):
    return a * 3 + q, b * 3 + a, c * 3 + b, q * 3
def fa(a, b, c, q):
    return a + q, b, c, q
def fb(a, b, c, q):
    return a, b + a, c, q
def fc(a, b, c, q):
    return a, b, c + b, q
funcs = {'A':fa, 'B': fb, 'C':fc, '?':fq}
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    a, b, c, q = funcs[s](a, b, c, q)

ans = c % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

N = int(input())
L = [int(x) for x in input().split()]

L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in range(i + 2, N):
        k = j - 1
        while L[k] > L[j] - L[i] and k > i:
            k -= 1
        ans += j - k - 1
print(ans)

### FIXED CODE ###

N = int(input())
L = [int(x) for x in input().split()]

import bisect
L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in reversed(range(i + 1, N - 1)):
        k = bisect.bisect_left(L, L[i] + L[j], j)
        ans += k - j - 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
p = 1000000007
ans = 0  
for i in range(N- K +1):
  ans += ((A[N-1-i] - A[i])*comb(N-1-i, K-1, p))
  ans = ans % p
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
p = 1000000007
frac = [1]
for i in range(N):
  frac.append(frac[i]*(i+1)%p)

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=frac[n]
    b=frac[k]
    c=frac[n-k]
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  

ans = 0  
for i in range(N- K +1):
  ans += ((A[N-1-i] - A[i])*comb(N-1-i, K-1, p))
  ans = ans % p
print(ans)
### BUGGY CODE ###

import bisect
 
N, M = map(int, input().split(" "))
As = [0]+list(map(int, input().split(" ")))
As = sorted(As)
cnt = 0
cnt2 = 1
for _ in range(M):
  i = As[-1-cnt]  
  i = i>>cnt2
  if i < As[-1-cnt-1]:
    cnt += 1
    cnt2 = 1
    bisect.insort_left(As,i)
  else:
    cnt2 += 1
 
print(sum(As[:-cnt]))

### FIXED CODE ###

import heapq
 
N, M = map(int, input().split(" "))
As = [-i for i in map(int, input().split(" "))]
As.sort()
heapq.heapify(As)

for _ in range(M):
  i = - heapq.heappop(As)
  i = i >> 1
  heapq.heappush(As,-i)

print(-sum(As))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

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

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            prev = dp[i][j]
            curr = dp[i + 1][j]

            curr[0] = (curr[0] + prev[0]) % MOD
            curr[1] = (curr[1] + prev[0] + prev[1]) % MOD
            curr[2] = (curr[2] + prev[0] + prev[1] + prev[2]) % MOD

            # 選択する
            if j - x < 0: continue
            prev_x = dp[i][j - x]

            curr[1] = (curr[1] + prev_x[0] + prev_x[1]) % MOD
            curr[2] = (curr[2] + prev_x[0] + prev_x[1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

N = int(input())
H = [int(x) for x in input().split()]
c = [0 for x in range(len(H))]

for i in range(len(H)-1):
    k = 0
    while H[i+k+1] <= H[i+k]:
        c[i] += 1
        k += 1
        if i+k >= len(H)-1:
            break

print(max(c))

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
x = 0
ans = 0

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

from collections import deque
s = deque(input())
q = int(input())

for i in range(q):
    t = input()
    if len(t) == 1:
        s.reverse()
    else:
        if t[2] == "1":
            s.appendleft(t[4])
        else:
            s.append(t[4])

print(*s, sep="")



### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
rev = 0

for i in range(q):
    t = input()
    if rev == 0:
        if len(t) == 1:
            rev = 1
        else:
            if t[2] == "1":
                s.appendleft(t[4])
            else:
                s.append(t[4])
    else:
        if len(t) == 1:
            rev = 0
        else:
            if t[2] == "1":
                s.append(t[4])
            else:
                s.appendleft(t[4])

if rev == 1:
    s.reverse()
print(*s, sep="")
### BUGGY CODE ###

def main():
    n = int(input())
    a_lst = [int(input()) for _ in range(n)]

    new_lst = []
    for i in range(n):
        a = a_lst[i]
        if a not in new_lst:
            new_lst.append(a)
        else:
            new_lst.remove(a)

    count = len(new_lst)
    print(count)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a_lst = [int(input()) for _ in range(n)]
    a_lst.sort()

    count = 0
    tmp = 0
    number = a_lst[0]

    for i in range(n):

        if a_lst[i] == number:
            tmp += 1

            if i == n - 1:
                if tmp % 2 != 0:
                    count += 1

        else:
            number = a_lst[i]

            if tmp % 2 == 0:
                tmp = 1
                continue
            else:
                count += 1
                tmp = 1

    if n > 1:
        if a_lst[-1] != a_lst[-2]:
            count += 1

    print(count)


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

from math import ceil
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 10**10
x = 0
for i in range(N-1):
    x+=A[i]
    ans = min(ans, abs(sum(A)-2*x))
print(ans)

### FIXED CODE ###

from math import ceil
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
Asum = sum(A)
ans = 10**10
x = 0
for i in range(N-1):
    x+=A[i]
    ans = min(ans, abs(Asum-2*x))
print(ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[-1]+a[i])
bb = [0]
for i in range(m):
    bb.append(bb[-1]+b[i])
ans = 0
for i in range(n+1):
    if aa[i] > k:
        break
    j = m
    while aa[i] + bb[j] > k and j > 0:
        j -= 1
    ans = max(ans, i+j)
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = [0]
for i in a:
    aa.append(aa[-1]+i)
bb = [0]
for i in b:
    bb.append(bb[-1]+i)
ans = 0
j = m
for i in range(n+1):
    if aa[i] > k:
        break
    while aa[i] + bb[j] > k and j > 0:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

n = int(input())
c = 0
i = 0
for p in range(2, n): #nが合成数
  if n%p == 0:
    c += 1
    n /= p
    i += 1
if n != 1 and i == 0: #nが素数
  c += 1
print(c)

### FIXED CODE ###

n = int(input())
c = 0
for p in range(2, int(n**0.5)+1): #nが合成数
  e = 0
  while n%p == 0:
    n //= p
    e += 1
  i = 1
  while e >= i:
    e -= i
    c += 1
    i += 1
if n != 1: #nが素数
  c += 1
print(c)
### BUGGY CODE ###

import sys
N = int(input())
A = list(input().split())
flag = 0
for i in range(0, N):
    for j in range(0, N):
        if i!=j and A[i] == A[j]:
            flag = 1
if flag == 1:
    print("NO")
    sys.stdout.flush
else:
    print("YES")
    sys.stdout.flush

### FIXED CODE ###

import sys
N = int(input())
A = list(input().split())
def has(s):
    return len(s) != len(set(s))
B = A
B = has(A) 
if B == False:
    print("YES")
    sys.stdout.flush
else:
    print("NO")
    sys.stdout.flush
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h = [0] + h
dp = [float("inf")]*(n+1)
dp[1] = 0
for i in range(1,n+1):
    for j in range(i+1,min(i+k+1,n+1)):
        dp[j] = min(abs(h[i] - h[j]) + dp[i], dp[j])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(abs(h[i-j] - h[i]) + dp[i-j], dp[i])
print(dp[-1])
### BUGGY CODE ###

from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)


### FIXED CODE ###

from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[p[0]][p[1]] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

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

n = int(input())

arr = []

for i in range(n):
	arr.append(int(input()))


dp = [0 for i in range(n)]

for i in range(n):
	dp[i] = 1
	for j in range(i):
		if arr[i] > arr[j]:
			dp[i] = max(dp[i], dp[j] + 1)

print max(dp)



### FIXED CODE ###

import bisect
n = int(input())
inf = float("inf")
arr = [int(input()) for _ in xrange(n)]

dp = [inf for _ in xrange(n)]

for i in arr:
	ind = bisect.bisect_left(dp,i)
	dp[ind] = i

print bisect.bisect_left(dp,inf)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0
mod = 10**9+7
for i in range(n-1):
  for j in range(i,n):
    count = count + (l[i]^l[j])%mod
print(count%mod)
  

### FIXED CODE ###

def main():
    import sys 
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    c1 = [0]*60
    c0 = [0]*60
    mod = 10**9+7

    for i in l:
        for j in range(60):
            if (i >> j) & 1:
                c1[j] += 1
            else:
                c0[j] += 1

    ans = 0
    ni = 1
    for i in range(60):
        ans += (c1[i]*c0[i]*ni)%mod
        ans %= mod
        ni = ni*2%mod
    print(ans%mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

h,w=map(int,input().split())
A=[0]*h
s=[[0]*w for i in range(h)]
t=[[0]*h for i in range(w)]

for i in range(h):
    A[i]=[1 if i=='.' else 0 for i in list(input())]

for ip,a in enumerate(A):
    p1=[]
    p2=[]
    if a[0]==1:p1.append(0)
    for i in range(1,len(a)):
        if a[i-1]==0 and a[i]==1:p1.append(i)
        if a[i-1]==1 and a[i]==0:p2.append(i)
    if a[-1]==1:p2.append(len(a))
        
    
    for s1,g1 in zip(p1,p2):
        for j in range(s1,g1):
            s[ip][j]=g1-s1
            
for ip,a in enumerate(zip(*A)):
    p1=[]
    p2=[]
    if a[0]==1:p1.append(0)
    for i in range(1,len(a)):
        if a[i-1]==0 and a[i]==1:p1.append(i)
        if a[i-1]==1 and a[i]==0:p2.append(i)
    if a[-1]==1:p2.append(len(a))
        
    
    for s1,g1 in zip(p1,p2):
        for j in range(s1,g1):
            t[ip][j]=g1-s1

ans=0
for i in range(w):
	for j in range(h):
		ans=max(ans,s[j][i]+t[i][j])
print(ans-1)

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(lambda x:False if x=='#' else True ,input())) for i in range(H)]

L=[[0]*W for i in range(H)]
R=[[0]*W for i in range(H)]
D=[[0]*W for i in range(H)]
U=[[0]*W for i in range(H)]


for i in range(H):
	for j in range(1,W):
		if A[i][j]:
			L[i][j]=int(A[i][j-1])+L[i][j-1]

for i in range(H):
	for j in range(W-1)[::-1]:
		if A[i][j]:
			R[i][j]=int(A[i][j+1])+R[i][j+1]

for i in range(1,H):
	for j in range(W):
		if A[i][j]:
			U[i][j]=int(A[i-1][j])+U[i-1][j]


for i in range(H-1)[::-1]:
	for j in range(W):
		if A[i][j]:
			D[i][j]=int(A[i+1][j])+D[i+1][j]

ans=0
for i in range(H):
	for j in range(W):
		ans=max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]+1)

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

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.append([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()




### FIXED CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.appendleft([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()
### BUGGY CODE ###

from collections import deque,Counter
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
ans = [0]*n
frd = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
    ans[a] -= 1
    ans[b] -= 1

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if uni[c] == uni[d]:
        ans[c] -= 1
        ans[d] -= 1

for i in range(n): ans[i] += cnt[uni[i]] - 1

print(*ans)

### FIXED CODE ###

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")
### BUGGY CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            del D[it]
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

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

MOD = 1000000007

def solve2(Xs, Ys):
    cell_num = (len(Xs) - 1) * (len(Ys) - 1)
    if len(Xs) < 2 or len(Ys) < 2:
        return 0

    area = (Xs[-1] - Xs[0]) * (Ys[-1] - Ys[0])
    ans = area * cell_num
    ans %= MOD
    return ans

def solve(Xs, Ys):
    if len(Xs) <= 3 and len(Ys) <= 3:
        return solve2(Xs, Ys)

    ans = solve2(Xs, Ys)
    for i in range(1, len(Xs) // 2):
        ans += solve2(Xs[i:-i], Ys)
        ans %= MOD
    for i in range(1, len(Ys) // 2):
        ans += solve2(Xs, Ys[i:-i])
        ans %= MOD
    ans += solve(Xs[1:-1], Ys[1:-1])
    ans %= MOD
    return ans

N, M = map(int, input().split())
Xs = list(map(int, input().split()))
Ys = list(map(int, input().split()))
print(solve(Xs, Ys))


### FIXED CODE ###

#!/usr/bin/env python3
#
# まず1次元で考える
#   |  |   |  |
#   a  b   c  d
# とあるとき、長さの合計は
#  (b-a) + (c-a) + (d-a) + (c-b) + (d-b) + (d-c)
# = 3d + c - b - 3a
# これは、各点の座標を、<自分より左にある点の数> - <自分より右にある点の数> でかけたものの和である
#
# もとめる面積は X座標、Y座標それぞれについて蒸気を計算した積

MOD = 1000000007

def len_sum(Xs):
    size = len(Xs)
    ret = 0
    n = len(Xs) - 1
    # 負の値にMODをとることを防ぐため、座標の大きい点から計算する
    for x in reversed(Xs):
        ret += n * x
        ret %= MOD
        n -= 2
    return ret

def solve(Xs, Ys):
    x_len_sum = len_sum(Xs)
    y_len_sum = len_sum(Ys)
    return (x_len_sum * y_len_sum) % MOD

N, M = map(int, input().split())
Xs = list(map(int, input().split()))
Ys = list(map(int, input().split()))
print(solve(Xs, Ys))
### BUGGY CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    comb = set()
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if i == j or j == k or i == k:
                    continue
                elif i + j + k == x:
                    sort_9 = sorted((i, j, k))
                    sort_9 = tuple(sort_9)
                    comb.add(sort_9)
    print(len(comb))



### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    comb = set()
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i == j or j == k or i == k:
                    continue
                elif i + j + k == x:
                    sort_9 = sorted((i, j, k))
                    comb.add(tuple(sort_9))

    print(len(comb))
### BUGGY CODE ###

N=int(input())
S=list(input())
flag=1
count=0
for i in range(1000):
  numS=''
  flag=1
  if i<10:
    numS='00'+str(i)
  elif i<100:
    numS='0'+str(i)
  else:
    numS=str(i)
  for j in range(N):
    if numS[0]==S[j]:
      for k in range(j+1,N):
        if numS[1]==S[k]:
          if numS[2] in S[k+1:]:
            count+=1
            flag=0
            break
          else:
            flag=0
            break
        elif k==N-1 and flag==1:
          flag=0
    if flag==0:
      break

print(count)

### FIXED CODE ###

N = int(input())
S = input()
s1 = set()
s2 = set()
s3 = set()

for i in S:
  for j in s2:
    s3.add(j+i)
  for k in s1:
    s2.add(k+i)
  s1.add(i)
print(len(s3))