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

import math
import numpy as np
import re


def inputs(): return [int(s) for s in input().split()]


def main():
    s = input()
    cnt = 0
    s = s.replace('A', '1').replace('BC', '0')
    arr = re.split('[A-C]', s)
    arr = [list(x) for x in arr]

    flag = True
    while flag:
        flag = False
        for a in arr:

            for i in range(len(a)-1):
                if a[i] > a[i + 1]:
                    a[i], a[i + 1] = a[i+1], a[i]
                    cnt += 1
                    flag = True
    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import numpy as np
import re


def inputs(): return [int(s) for s in input().split()]


def main():
    s = input()
    cnt = 0
    s = s.replace('A', '1').replace('BC', '0')
    arr = re.split('[A-C]', s)
    arr = [list(x) for x in arr]
    flag = True
    while flag:
        flag = False
        for a in arr:
            tmp = 0
            for i in a:
                i = int(i)
                tmp += i
                if i is 0:
                    cnt += tmp

    return cnt


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

N = int(input())
Al = [int(i) for i in input().split()]

ans = 0
for i in range(len(Al)):
    for j in range(len(Al)):
        if i == j:
            continue
        if Al[i] % Al[j] == 0:
            break
    else:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
Al = sorted([int(i) for i in input().split()])
maxAl = Al[-1]
markl = [-1] * (maxAl+1)

for i in Al:
    if markl[i] == 1:
        continue
    if markl[i] == 0:
        markl[i] = 1
        continue
    markl[i] = 0
    p = i*2
    while p <= maxAl:
        markl[p] = 1
        p += i
print(markl.count(0))
### BUGGY CODE ###

A, B, N = input().split()
max = 0
for i in range(int(N)+1):
    temp = i/int(B) -int(i/int(B))
    if temp > max:
        max = temp

print(int(max*int(A)))

### FIXED CODE ###

A, B, N = input().split()
f = 0
if int(N) >= int(B):
    f = (int(B) - 1) / int(B)
    f = f - int(f)
else:
    f = int(N) / int(B)
    f = f - int(f)

print(int(f*int(A)))
### BUGGY CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

ans = 1
for l in range(1, k + 1):
    ans += combination(n, l) * combination(n - 1, l)
    ans %= MOD
print(ans % MOD)


### FIXED CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

    def comb(self, n, r):
        if r < 0 or n < r or r < 0:
            return 0
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.MOD



n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

coef = BinomialCoefficient(n + 1, MOD)
ans = 1
for l in range(1, k + 1):
    ans += coef.comb(n, l) * coef.comb(n - 1, l)
    ans %= MOD
print(ans % MOD)
### BUGGY CODE ###

import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    zero, inf, ng = 0, 0, 0
    for x, y in F:
        if x == 0 and y == 0: ng += 1
        elif x == 0: inf += 1
        elif y == 0: zero += 1
        else: 
            tan = Fraction(y, x)
            if tan in D: D[tan] += 1
            else: D[tan] = 1

    ans = 1
    ans *= (pow(2, zero, mod) + pow(2, inf, mod) - 1) % mod
    ans %= mod
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            ne, de = key.numerator, key.denominator
            op = (0 if Fraction(-de, ne) not in D else D[Fraction(-de, ne)])
            used |= {Fraction(-de, ne)}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans += ng
    ans %= mod
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from math import gcd
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    zero, inf, ng = 0, 0, 0
    for x, y in F:
        if x == 0 and y == 0: ng += 1
        elif x == 0: inf += 1
        elif y == 0: zero += 1
        else: 
            g = gcd(abs(x), abs(y))
            if x < 0:
                y *= -1
                x *= -1
            x //= g
            y //= g
            tan = (y, x)
            if tan in D: D[tan] += 1
            else: D[tan] = 1

    ans = 1
    ans *= (pow(2, zero, mod) + pow(2, inf, mod) - 1) % mod
    ans %= mod
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            y, x = key
            rev = ((-x, y) if y > 0 else (x, -y))
            op = (0 if rev not in D else D[rev])
            used |= {rev}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans += ng
    ans %= mod
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

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

s = list(input())
n = int(input())
sl = []
fl = []
flag = True
for _ in range(n):
    q = list(map(str, input().split()))
    if len(q) == 1:
        if flag:
            flag = False
        else:
            flag = True
    if len(q) == 3:
        if q[1] == "1":
            if flag:
                s = list(q[2])+s
            else:
                s = s+list(q[2])
        else:
            if flag:
                s = s+list(q[2])
            else:
                s = list(q[2])+s
if flag == False:
    s.reverse()
print("".join(s))

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
n = int(input())
flag = True
for _ in range(n):
    q = list(map(str, input().split()))
    if len(q) == 1:
        if flag:
            flag = False
        else:
            flag = True
    if len(q) == 3:
        if (q[1] == "1" and flag == False) or (q[1] == "2" and flag):
            s.append(q[2])
        else:
            s.appendleft(q[2])
if flag == False:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    R, C, K = map(int, input().split())

    G = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        r -= 1
        c -= 1
        G[r][c] = v

    dp = [[[0] * 4 for _ in range(C)] for _ in range(R)]

    for r in range(R):
        for c in range(C):
            for i in range(4):
                if r > 0:
                    dp[r][c][0] = max(dp[r][c][0], dp[r - 1][c][i])
                if c > 0:
                    dp[r][c][i] = max(dp[r][c][i], dp[r][c - 1][i])
            for i in range(2, -1, -1):
                dp[r][c][i + 1] = max(dp[r][c][i + 1], dp[r][c][i] + G[r][c])

    # print(f'{dp=}')
    ans = max(dp[-1][-1])
    print(ans)


if __name__ == '__main__':
    main()

# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


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

import sys 
from collections import deque
l = deque(sys.stdin.readlines())
n, m = (int(x) for x in l[0].split())
l.popleft()
ab = deque()
for i in range(m):
  a, b = tuple(int(x) for x in l[i].split())
  if a == 1 or b == n: ab.append((a, b)) 
  
for i in ab:
  if i[0] == 1:
      if (i[1], n) in ab: print('POSSIBLE'); exit()

print('IMPOSSIBLE')

### FIXED CODE ###

n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] *2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
from collections import Counter

def resolve():
    s = input()

    mod_table = np.zeros(shape=len(s), dtype=int)
    for i in reversed(range(len(s) - 1)):
        mod_table[i] = int(s[i:]) % 2019

    count = Counter(mod_table)
    vals = np.array(list(count.values()))

    ans = sum((vals * (vals - 1)) / 2)
    print(int(ans))
resolve()

### FIXED CODE ###

def resolve():
    s = [int(i) for i in input()]
    p_cnt = 0

    p = 2019

    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(len(s)):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)


    print(p_cnt)
    
resolve()
### BUGGY CODE ###

S = input()
Q = int(input())

a = 0
for i in range(Q):
    t = input()
    if t == "1":
        if a == 0:
            a = 1
        else:
            a = 0
    else:
        t,f,c = t.split()
        if f == "1":
            if a == 0:
                S = c + S
            else:
                S = S + c
        else:
            if a == 0:
                S = S + c
            else:
                S = c + S
            
if a == 1:
    S = S[::-1]
    
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())

a = 0
for i in range(Q):
    t = input()
    if t == "1":
        if a == 0:
            a = 1
        else:
            a = 0
    else:
        t,f,c = t.split()
        if f == "1":
            if a == 0:
                S.appendleft(c)
            else:
                S.append(c)
        else:
            if a == 0:
                S.append(c)
            else:
                S.appendleft(c)
            
if a == 1:
    S = reversed(S)
    
S = ''.join(S)
print(S)
### BUGGY CODE ###

#!/usr/bin/env python3
#abc126 e

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

G = [[] for _ in range(N)]
for i in XYZ:
    for j in range(1,N+1):
        if i[0] == j:
            G[j-1].append(i[1])
        if i[1] == j:
            G[j-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか
def DFS(G,start):
    check[start-1] = True
    for i in G[start-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#abc126 e

import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

G = [[] for _ in range(N)]

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか

def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
dp={():0}
for i in range(m):
  a,b=ab[i]
  sc=set(c[i])
  dptmp={}
  for k,v in dp.items():
    s=set(k)
    s|=sc
    t=tuple(sorted(list(s)))
    dptmp[t]=min(v+a,dp[t] if t in dp else float('inf'),dptmp[t] if t in dptmp else float('inf'))
  dp.update(dptmp)

t=tuple(range(1,n+1))
if t in dp:
  print(dp[t])
else:
  print(-1)


### FIXED CODE ###

n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
dp={'0'*n:0}
for i in range(m):
  a,b=ab[i]
  ci=c[i]
  dptmp={}
  for k,v in dp.items():
    s=list(k)
    for cii in ci:
      s[cii-1]='1'
    t=''.join(s)
    dptmp[t]=min(v+a,dp[t] if t in dp else float('inf'),dptmp[t] if t in dptmp else float('inf'))
  dp.update(dptmp)

t='1'*n
if t in dp:
  print(dp[t])
else:
  print(-1)
#print(dp)
### BUGGY CODE ###

import itertools
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    hoge = tuple(map(int, input().split()))
    sumn = 0
    mod = 10 ** 9 + 7
    for pair in itertools.combinations(hoge, 2):
        sumn += (pair[0] * pair[1])
        sumn %= mod
    print(sumn)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    nums = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    num_sum = sum(nums)
    part_sum = sum(map(lambda x: x**2, nums)) # naname

    print((num_sum**2 - part_sum) // 2 % mod)


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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if i + k == 2 * j:
                pass
            elif S[i] == S[j] or S[j] == S[k] or S[i] == S[k]:
                pass
            else:
                cnt += 1
print(cnt)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

cnt = 0
cnt += S.count("R") * S.count("G") * S.count("B")

# for i in range(1, N - 1):
#     for j in range(i + 1, N):
#         k = 2 * j - i
#         if k > N :
#             continue
#         if S[i - 1] != S[j - 1] and S[j-1] != S[k-1] and S[i -1] != S[k-1]:
#             cnt -= 1

for k in range(N):
    for j in range(k):
        i = 2 * j - k
        if i < 0:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            cnt -= 1 

print(cnt)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
 
A = sorted(map(int,input().split()))[::-1]
B = sorted(map(int,input().split()))[::-1]
C = sorted(map(int,input().split()))[::-1]
 
AB = sorted([a+b for a in A for b in B])[::-1]
 
ans = sorted([ab + c for ab in AB[:k] for c in C])[::-1]
 
for i in ans[:k]:
    print(i)

### FIXED CODE ###

# coding: utf-8
# Your code here!

x,y,z,k = map(int,input().split())

A = sorted(map(int,input().split()))[::-1]
B = sorted(map(int,input().split()))[::-1]
C = sorted(map(int,input().split()))[::-1]

AB = sorted([a+b for a in A for b in B])[::-1]

ans = sorted([ab + c for ab in AB[:k] for c in C])[::-1]

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

N,K = map(int,input().split(' '))
a = list(map(int,input().split(' ')))

cost = list()
cost.append(0)
for i in range(1,N):
    step_min = 10**9
    for j in range(1,min(i+1,K+1)):
        step_cost = abs(a[i] - a[i-j]) + cost[i-j]
        step_min = step_cost if step_cost < step_min else step_min
    cost.append(step_min)

print(cost[-1])

### FIXED CODE ###

import numpy as np

N,K = map(int,input().split(' '))
a = np.array(list(map(int,input().split(' '))))

cost = np.full(N,10**9)
cost[0] = 0
for i in range(1 , N):
    
    size =  min(i,K)
    cost[i] = (np.abs(a[i] - a[i-size:i]) + cost[i-size:i]).min()

print(int(cost[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    Nmax = 10**6+1

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

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

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

import sys
import collections

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
il = list(set(a))
li = collections.Counter(a)
q = ri()
res = []
bc = [rl() for _ in range(q)]
for vvv in bc:
    b, c = vvv
    if b in il:
        if c in il:
            li[c] += li[b]
        else:
            li[c] = li[b]
            il.append(c)
        li[b] = 0
        il.remove(b)
    ans = 0
    for k, v in li.items():
        ans += k*v
    res.append(ans)
for aaa in res:
    print(aaa)



### FIXED CODE ###

import sys
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
t = sum(a)
cnt_li = [0]*10**5
for i in a:
    cnt_li[i-1] += 1

for _ in range(ri()):
    b, c = rm()
    t += (c-b)*cnt_li[b-1]
    print(t)
    cnt_li[c-1] += cnt_li[b-1]
    cnt_li[b-1] = 0
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]

bef = 1
for i in range(k):
    bef *= a[i]
for i in range(k, n):
    val = bef // a[i-k] * a[i]
    if val > bef:
        print('Yes')
    else:
        print('No')
    bef = val


### FIXED CODE ###

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
bef = 0
for i in range(k, n):
    val = a[i]
    bef = a[i-k]
    if val > bef:
        print('Yes')
    else:
        print('No')
    bef = val
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
k = 0

for i in range(n - 1):
    for l in range(i + 1, n):
            k += a[i] * a[l]

x = k % (10 ** 9 + 7)
print(x)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
k = 0
num = sum(a)
t = 10 ** 9 + 7

for i in a:
    num -= i
    k += num * i

ans = k % t
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
h,w,n = map(int,input().split())
s = [[0 for j in range(w+2)] for i in range(h+2)]
#print(s)
for i in range(0,n):
    x,y = map(int,input().split())
    s[x-1][y-1] += 1
    s[x-1][y] += 1
    s[x-1][y+1] += 1
    s[x][y-1] += 1
    s[x][y] += 1
    s[x][y+1] += 1
    s[x+1][y-1] += 1
    s[x+1][y] += 1
    s[x+1][y+1] += 1

#print(s)
ans = [0] * 10
for i in range(2,h):
    for j in range(2,w):
        ans[s[i][j]] += 1
for i in range(0,10):
    print(ans[i])


### FIXED CODE ###

def add_memo(tate,yoko):
    global memo
    if 2 <= tate <= h-1:
        if 2 <= yoko <= w-1:
            memo.append([tate,yoko])

h,w,n = map(int,input().split())
#print(s)
memo = []
for i in range(0,n):
    x,y = map(int,input().split())
    add_memo(x-1,y-1)
    add_memo(x-1,y)
    add_memo(x-1,y+1)
    add_memo(x,y-1)
    add_memo(x,y)
    add_memo(x,y+1)
    add_memo(x+1,y-1)
    add_memo(x+1,y)
    add_memo(x+1,y+1)

memo.sort()
ans = [0] * 10
ans[0] = (h-2)*(w-2)
tmp_x = 0
tmp_y = 0
count = 0
for i in range(0,len(memo)):
    if tmp_x == memo[i][0] and tmp_y == memo[i][1]:
        ans[count] -= 1
        count += 1
        ans[count] += 1
    else:
        ans[0] -= 1
        count = 1
        ans[count] += 1
    tmp_x = memo[i][0]
    tmp_y = memo[i][1]
#    print(memo[i],count)

for i in range(0,10):
    print(ans[i])
### BUGGY CODE ###

input()
S = list(input())
count = 0
limit = 10**9 + 7
for mask in range(1, 2 << len(S)-1):
	temp = {}
	for i, v in enumerate(S):
		if 0 != mask & (1 << i):
			if v in temp:
				break
			temp[v] = True
	else:
		count += 1
		if limit <= count:
			break
print(count)


### FIXED CODE ###

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

mod = 10**9+7
R = 1
for w in set(S):
	#print(w, S.count(w))
	R *= S.count(w) + 1
	R %= mod
print(R - 1)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]

dp = [0]*(W+1)
for w,v in a:
    for j in range(w,W+1)[::-1]:
        dp[j] = max(dp[j], dp[j-w] + v)
print(dp[W])

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp = np.array([0]*(W+1))
for w,v in a:
    ed = W+1-w
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[0:W+1-w] + v)
print(dp[W])
### BUGGY CODE ###

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

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split())) 
l = [0] * N


for i in range(N-1):
    l[A[i]-1] += 1
for j in l:
    print(j)