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

import math

n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7

# ans = 2 ** n - 1

def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y
	
ans = pow_by_binary_exponentiation(2, n, MOD)

ans -= 1

fac = [1]
inv = [1]

for i in range(1, n + 1) :
	fac.append(fac[-1] * i % MOD)
	inv.append(pow(fac[-1], MOD - 2, MOD))

ans -=  fac[n] * inv[a] * inv[n - a] % MOD
ans -=  fac[n] * inv[b] * inv[n - b] % MOD

print(ans % MOD)

### FIXED CODE ###

n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7

# でっかい数の n C a
def comb(n, a):
	ret = 1
	# 分子部分の計算
	for i in range(n - a + 1, n + 1):
		ret *= i
		ret %= MOD
	# 分母部分の計算
	for i in range(1, a + 1):
		ret *= pow(i, MOD - 2, MOD)
		ret %= MOD
	return ret
	
ans = pow(2, n, MOD) - 1
ans -= comb(n, a)
ans -= comb(n, b)
print(ans % MOD)
### BUGGY CODE ###

import itertools
import math


def gcd(a: int, b: int, c: int) -> int:
    return math.gcd(math.gcd(a, b), c)


def main() -> None:
    k = int(input())

    s = sum(gcd(a, b, c) for a, b, c in itertools.product(range(1, k + 1), repeat=3))
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import itertools
import math


def gcd(a: int, b: int, c: int) -> int:
    return math.gcd(math.gcd(a, b), c)


def main() -> None:
    k = int(input())

    one_to_k = range(1, k + 1)
    s1 = sum(one_to_k)
    s2 = sum(math.gcd(a, b) for a, b in itertools.combinations(one_to_k, 2))
    s3 = sum(gcd(a, b, c) for a, b, c in itertools.combinations(one_to_k, 3))
    print(s1 + 6 * s2 + 6 * s3)


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

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

if A == B:
    print(A)
else:
    for i in range(A, B+1):
        if A <= i <= A+K-1 or B-K+1<= i <= B:
            print(i)

### FIXED CODE ###

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

# for i in range(A, B+1):
#     if (A <= i and i <= A+K-1) or (B-K+1<= i and i <= B):
#         print(i)

S=set()

for i in range(A, min(B+1, A+K)):
    S.add(i)
for i in range(max(A, B-K+1), B+1):
    S.add(i)
for k in sorted(S):
    print(k)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a_i = [i - aa for i, aa in enumerate(a)]
a_j = [j + aa for j, aa in enumerate(a)]
ans = 0
for i in a_i:
    ans += a_j.count(i)    
print(ans)

### FIXED CODE ###

import collections

n = int(input())
a = [int(i) for i in input().split()]
a_i = [i - aa for i, aa in enumerate(a)]
a_j = [j + aa for j, aa in enumerate(a)]

ci = collections.Counter(a_i)
cj = collections.Counter(a_j)
ans = 0
for item, value in ci.items():
    if item in cj.keys():
        ans += cj[item] * ci[item]
print(ans)
### BUGGY CODE ###

# 毎回ソートすると間に合わん
# そもそも一番大きいやつは更新されないので、[b,c]についてcで降順ソートしたものを対象にする
# その時点で大きいものに更新されたやつは二度と更新されないので次回以降は省いたものだけ対象にできる
# orにぶたんでどこまでいけるか
import bisect

n, m = map(int, input().split())
arr = list(sorted(list(map(int, input().split()))))
bc = []
for _ in range(m):
    b, c = map(int, input().split())
    bc.append([b, c])

bc = list(sorted(bc, key=lambda x: x[1], reverse=True))
ans = 0

for bci in bc:
    d = bisect.bisect_left(arr, bci[1])
    g = arr[: min(d, bci[0])]
    arr = arr[min(d, bci[0]) :]
    ans += len(g) * bci[1]
print(ans + sum(arr))


### FIXED CODE ###

# 書き換える枚数は確定できる
# cの大きい順にしたものでaの小さい順にしたものを置き換えるイメージ
# なんか尺取っぽくなった

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

bcs = []
for _ in range(m):
    bc = list(map(int, input().split()))
    bcs.append(bc)

bcs = sorted(bcs, key=lambda x: x[1], reverse=True)
ans = 0

i = 0
for b in bcs:
    while i < n and arr[i] < b[1] and b[0] > 0:
        ans += b[1]
        b[0] -= 1
        i += 1
print(ans + sum(arr[i:]))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

c = 0
for r in range(N + 1):
	for g in range(N + 1):
		if N < r * R + g * G:
			break
		f = (N - r * R - g * G) % B
		b = (N - r * R - g * G) // B
		if not f and (0 <= b) and (N == (r * R + g * G + b * B)): 
			#print(r, g, b)
			c += 1
print(c)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

c = 0
for r in range(0, N + 1, R):
	for g in range(0, N + 1, G):
		if N < r + g:
			break
		d = N - r - g
		if not d % B:
			c += 1
	
"""
	for g in range(N + 1):
		if N < r * R + g * G:
			break
		x = (N - r * R - g * G)
		if not (x % B) and (0 <= (x // B)):
			#print(r, g, b)
			c += 1
"""
print(c)
### BUGGY CODE ###

a,b,c,k = map(int, input().split())
ans = 0
if a==b:
    ans = 0
else:
    for i in range(k):
        a1 = b+c
        b1 = c+a
        c1 = a+b
        a = a1
        b = b1
        c = c1
    if abs(a-b)>=10**18:
        ans = 'Unfair'
    else:
        ans = a-b
print(ans)

### FIXED CODE ###

a,b,c,k = map(int, input().split())
print(0 if a==b else a-b if k%2==0 else b-a)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
k=0
l=0
for i in range(N):
    for j in range(i+1):
        if P[i]<=P[j]:
            k+=1
        if k ==i+1:
            l+=1
    k=0
print(l)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 1
min_num = min(P[0:1])
for i in range(1,N):
    if P[i] <= min_num:
        count+=1
        min_num = P[i]
print(count)
### BUGGY CODE ###

import math 

K  = int(input())
total  = 0

for s in range(1,K+1):
    for t in range(1,K+1):
        for u in range(1,K+1):
            # print(s,t,u,math.gcd(math.gcd(s,t),u))
            total +=math.gcd(math.gcd(s,t),u)
2
print(total)


### FIXED CODE ###

import math 

K  = int(input())
total  = 0

for s in range(1,K+1):
    for t in range(1,K+1):
        alpha = math.gcd(s,t)
        if alpha == 1:
            total += K
            continue
        for u in range(1,K+1):
            # print(s,t,u,math.gcd(alpha,u))
            total +=math.gcd(alpha,u)

print(total)
### BUGGY CODE ###

N = int(input())
gacha_list = []
output = 0

for i in range(N):
  input_line = input()
  gacha_list.append(input_line)

while len(gacha_list) > 0:
  result = gacha_list[0]
  indexes = [i for i, x in enumerate(gacha_list) if x == result]
  for i in sorted(indexes, reverse=True):
    gacha_list.pop(i)
  output += 1
  
print(output)

### FIXED CODE ###

N = int(input())
gacha_list = set()

for i in range(N):
  input_line = input()
  if input_line not in gacha_list:
    gacha_list.add(input_line)
    
print(len(gacha_list))
### BUGGY CODE ###

s = input()
n = len(s)
count = 0

def check(ij):
    ss = int(s[ij[0]-1:ij[1]])
    if ss % 2019 == 0:
        return True
    else:
        return False
    

def dfs(ij):
    global count
    if len(ij) == 2:
        if check(ij):
            count += 1
    elif len(ij) == 1:
        for k in range(ij[0]+3, n+1):
            ij.append(k)
            dfs(ij)
            ij.pop()
    else:
        for k in range(1, n-2):
            ij.append(k)
            dfs(ij)
            ij.pop()
            
dfs([])
print(count)

### FIXED CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    d %= 2019
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)
### BUGGY CODE ###

# C Sum of product of pairs

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

s = 0
for i in range(N-1):
  for j in range(i+1, N):
    s += A[i] * A[j]
    
print(s % (10**9 + 7))

### FIXED CODE ###

# C Sum of product of pairs

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

s = 0
old = 0
for i in range(N-1):
  old += A[i]
  s += old * A[i+1]
        
print(s % (10**9 + 7))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def popcount(n):
        cnt = 0
        for b in range(20):
            cnt += (n >> b) & 1
        return cnt

    n = int(input())
    X = input()
    one = X.count("1")

    for i in range(n):
        x = list(X)
        cnt = one + 1 if x[i] == "0" else one - 1
        x[i] = "1" if x[i] == "0" else "0"
        x = int("".join(x), 2)
        res = 0
        while x:
            if res != 0:
                cnt = popcount(x)
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()
    cnt_init = X.count("1")
    x = int(X, 2)
    a = x % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            y = (a + pow(2, n - i - 1, cnt)) % cnt
        else:
            cnt = cnt_init - 1
            if cnt == 0:
                print(0)
                continue
            y = (b - pow(2, n - i - 1, cnt)) % cnt

        res = 1
        while y:
            cnt = bin(y).count("1")
            y %= cnt
            res += 1
        print(res)


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

from itertools import product
def gcd(a, b, c):
    z = min(a, b, c)
    for i in range(z, 0, -1):
        if a%i==0 and b%i==0 and c%i==0:
            return i

k = int(input())

d = {}

totsum = 0
for config in list(product(range(1, k+1), range(1, k+1), range(1, k+1))):
    a, b, c = config
    if a==1 or b==1 or c==1: 
        totsum+=1
    elif a==b==c:
        totsum+=a
    else:
        try :
            ans = d[tuple(sorted((a, b, c)))]
        except: 
            ans = gcd(a, b, c)
            d[tuple(sorted((a, b, c)))] = ans

        totsum += ans
# print(d)
print(totsum)

### FIXED CODE ###

k = int(input())
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    H, W = read_values()
    C = tuple(read_index())
    D = tuple(read_index())
    S = [input().strip() for _ in range(H)]

    F = [10 ** 10] * (H * W)

    Q = [(0, C)]
    F[C[0] * W + C[1]] = 0
    while Q:
        c, (h, w) = heapq.heappop(Q)
        if (h, w) == D:
            print(c)
            return

        if F[h * W + w] > c:
            continue
        for d in (1, -1):
            if 0 <= w + d < W and S[h][w + d] == "." and F[h * W + w + d] > c:
                F[h * W + w + d] = c
                heapq.heappush(Q, (c, (h, w + d)))
            if 0 <= h + d < H and S[h + d][w] == "." and F[(h + d) * W + w] > c:
                F[(h + d) * W + w] = c
                heapq.heappush(Q, (c, (h + d, w)))
        
        for hh in range(h - 2, h + 3):
            for ww in range(w - 2, w + 3):
                if 0 <= ww < W and 0 <= hh < H and S[hh][ww] == "." and F[hh * W + ww] > c:
                    F[hh * W + ww] = c + 1
                    heapq.heappush(Q, (c + 1, (hh, ww)))
    
    print(-1)
            

if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    H, W = read_values()
    C = tuple(read_index())
    D = tuple(read_index())
    S = [input().strip() for _ in range(H)]

    F = [False] * (H * W)

    M = {C}
    Q = [C]
    F[C[0] * W + C[1]] = 0
    c = 0
    while len(M) > 0:
        M.clear()
        while Q:
            h, w = Q.pop()
            M.add((h, w))
            if (h, w) == D:
                print(c)
                return

            for d in (1, -1):
                if 0 <= w + d < W and S[h][w + d] == "." and not F[h * W + w + d]:
                    F[h * W + w + d] = True
                    Q.append((h, w + d))
                if 0 <= h + d < H and S[h + d][w] == "." and not F[(h + d) * W + w]:
                    F[(h + d) * W + w] = True
                    Q.append((h + d, w))
        for h, w in M:
            for hh in range(h - 2, h + 3):
                for ww in range(w - 2, w + 3):
                    if 0 <= ww < W and 0 <= hh < H and S[hh][ww] == "." and not F[hh * W + ww]:
                        F[hh * W + ww] = True
                        Q.append((hh, ww))
        c += 1
    print(-1)
            

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

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())


def g(x, y, z):
    return (x + y + z) ** 2 - (x*y + y*z + z*x)


for n in range(1, N+1):
    num_dict = {}
    res = 0
    for x in range(1, 30):
        for y in range(1, 30):
            for z in range(1, 30):
                num = g(x, y, z)
                if num > 10 ** 4:
                    continue
                if num == n:
                    # print(f'{x}+{y}+{z}={num}')
                    if (x, y, z) in num_dict:
                        continue
                    # print('doesnt exist')
                    num_dict[(x, y, z)] = 1
                    res += 1
    print(res)


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())


def g(x, y, z):
    return (x + y + z) ** 2 - (x*y + y*z + z*x)


xyz_dict = defaultdict(int)
num_dict = defaultdict(int)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            num = g(x, y, z)
            if (x, y, z) in xyz_dict:
                continue
            xyz_dict[(x, y, z)] = 1
            num_dict[num] += 1


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

H,W = map(int,input().split())
S = []
heigth = [0] * (W+1)
for i in range(H):
    s = list(input()) + [0]
    length = 0
    for j in range(W+1):
        if s[j] == '.':
            length += 1
            heigth[j] += 1
        else:
            s[j] = 0
            if length > 0:
                s = s[:(j-length)] + [length]*length + s[j:]
                length = 0
            if heigth[j] > 0:
                for k in range(heigth[j]):
                    S[i - k - 1][j] += heigth[j] - 1
                heigth[j] = 0 
    S.append(s)

for j in range(W):
    if heigth[j] > 0:
        for k in range(heigth[j]):
            S[i - k][j] += heigth[j] - 1

print(max([max(S[i]) for i in range(H)]))

### FIXED CODE ###

H,W = map(int,input().split())
height, width_max, ans = [0] * (W+1), [0] * (W+1), 0
for i in range(H):
    s = input() + '#'
    length = 0
    for j in range(W+1):
        if s[j] == '.':
            length += 1
            height[j] += 1
        else:
            if length > 0:
                for k in range(j-length, j):
                    if width_max[k] < length:
                        width_max[k] = length
                length = 0
            if height[j] > 0:
                temp = width_max[j] + height[j] - 1
                if ans < temp:
                    ans = temp
                width_max[j], height[j] = 0, 0
for j in range(W):
    if height[j] > 0:
        temp = width_max[j] + height[j] - 1
        if ans < temp:
            ans = temp
print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
#s=list(input())

t=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        t.append(s[i:j+1])
        
t.sort()
t1=t[0]
t2=[t[0]]
for i in range(1,len(t)):
    if t1!=t[i]:
        t2.append(t[i])
        t1=t[i]
        
print(t2[k-1])        
        

### FIXED CODE ###

s=input()
k=int(input())
#s=list(input())

#t=[]
#for kk in range(k):
#    t.append(s)

t=["zzzzz"]*k

for i in range(len(s)):
    for j in range(i,min(len(s),i+k)):
        sij=s[i:j+1]
        for kk in range(k):
            if t[kk]==sij:
                break
        if t[kk]>sij:
            t[kk]=sij
            t.sort()
        
print(t[k-1])  
#print(t)
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
s=[]
for _ in range(m):
    b,c=map(int,input().split())
    s.append((b,c))

s=sorted(s,key=lambda x: x[1],reverse=True)
for i in range(m):
    for j in range(s[i][0]):
        if a[j]<s[i][1]:
            a[j]=s[i][1]
    a=sorted(a)
print(sum(a))

### FIXED CODE ###

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

for i in range(m):
    b,c=map(int,input().split())
    arr.append((b,c))

a=sorted(a)
arr=sorted(arr,key=lambda x:-x[1])

flag=0
left=0
for tup in arr:
    for i in range(left,min(left+tup[0],n)):
        if tup[1]>a[i]:
            a[i]=tup[1]
        else:
            flag=-1
            break
        if i==n-1:
            flag=-1
            break
    left+=tup[0]
    if flag==-1:
        break

print(sum(a))
### BUGGY CODE ###

n,q=map(int, input().split())
s=input()
cnt=[0]*(n-1)
for i in range(n-1):
  if s[i:i+2]=='AC':
    cnt[i]=1
for i in range(q):
  l,r=map(int, input().split())
  print(sum(cnt[l-1:r-1]))

### FIXED CODE ###

n,q=map(int, input().split())
s=input()
cnt=[0]*(n-1)
for i in range(n-1):
  if s[i:i+2]=='AC':
    cnt[i]=1
cnt2=[0]*(n)
for i in range(1,n):
  cnt2[i]=cnt2[i-1]+cnt[i-1]
for i in range(q):
  l,r=map(int, input().split())
  print(cnt2[r-1]-cnt2[l-1])
### BUGGY CODE ###

from math import hypot,atan2,pi,cos
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

K = 200000
ans = 0
for i in range(K+1):
    t1 = 2*pi*i/K - pi
    r = 0
    for x,y in XY:
        t2 = atan2(y,x)
        a,b = (t1,t2) if t1<t2 else (t2,t1)
        if b-a > 3*pi/2:
            a += 2*pi
            a,b = b,a
        d = hypot(x,y) * cos(b-a)
        if d > 0:
            r += d
    ans = max(ans, r)
print(ans)

### FIXED CODE ###

from math import hypot,atan2
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
xy = sorted(XY, key=lambda x:atan2(x[1],x[0]))
xy += xy

ans = 0
for i in range(N):
    sx = sy = 0
    for j in range(N):
        x,y = xy[i+j]
        sx += x
        sy += y
        d = hypot(sx,sy)
        if d > ans:
            ans = d
print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
F = [list(map(int, (input().split()))) for i in range(M)]
tmp = [[] for i in range(N)]

for i in range(M):
    tmp[F[i][0]-1].append(F[i][1])

for i in range(N):
    tmp[i].sort()
    
for i in range(M):
    print(('0'*(6-len(str(F[i][0]))) + str(F[i][0])) + '0'*(6-len(str(tmp[F[i][0]-1].index(F[i][1])+1))) + str(tmp[F[i][0]-1].index(F[i][1])+1))

### FIXED CODE ###

N, M = map(int, input().split())
#tmp = [[] for i in range(N)]
tmp = []
res = ['' for i in range(M)]
count = [1 for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    tmp.append([A,B,i])

tmp.sort(key=lambda tmp: tmp[1])

for i in range(M):
    res[tmp[i][2]] += '0'*(6-len(str(tmp[i][0]))) + str(tmp[i][0]) + '0'*(6-len(str(count[tmp[i][0]]))) + str(count[tmp[i][0]])
    count[tmp[i][0]] += 1

for i in range(M):
    print(res[i])
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    for i in range(l+1):
      for j in range(r, N+1):
        DP[i][j] += 1

  for _ in range(Q):
    p, q = map(int, input().split())
    print(DP[p][q])


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

  cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
  for i in range(1, N+1):
    for j in range(1, N+1):
      cum[i][j] = DP[i][j] + cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1]

  for _ in range(Q):
    p, q = map(int, input().split())
    print(cum[q][q] - cum[p-1][q] - cum[q][p-1] + cum[p-1][p-1])


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

n=int(input())
a=list(map(int, input().split()))
c=0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i]==a[j]:
            c+=1

if c==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
a.sort()
c=0
for i in range(n-1):
    if a[i]==a[i+1]:
        c+=1
        break
if c==0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

def main():
    s = str(input())
    q = int(input())
    lst = [list(map(str, input().split())) for _ in range(q)]
    switch = 0  # 0が通常　1が前

    for i in range(q):

        if lst[i][0] == '1':
            switch = 1 - switch

        else:
            f = lst[i][1]
            c = lst[i][2]

            if f == '1':  # 先頭に追加

                if switch == 0:
                    s = c + s

                else:
                    s = s + c

            else:

                if switch == 0:
                    s = s + c

                else:
                    s = c + s

    if switch == 1:
        s = s[::-1]
        
    print(s)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = str(input())
    q = int(input())
    lst = [list(map(str, input().split())) for _ in range(q)]
    switch = 0  # 0が通常　1が前

    str_lst = [s]
    front_lst = []
    for i in range(q):

        if lst[i][0] == '1':
            switch = 1 - switch

        else:
            f = lst[i][1]
            c = lst[i][2]

            if f == '1':  # 先頭に追加

                if switch == 0:
                    front_lst.append(c)

                else:
                    str_lst.append(c)

            else:

                if switch == 0:
                    str_lst.append(c)

                else:
                    front_lst.append(c)

    front = ''.join(front_lst)
    front = front[::-1]
    after = ''.join(str_lst)
    answer = front + after

    if switch == 1:
        answer = answer[::-1]

    print(answer)


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

from bisect import bisect_left

N = int(input())
l = []

for i in range(N):
    a = int(input())
    n = bisect_left(l,a)
    if n != 0:
        l[n-1] = a
    else:
        l = [a] + l
print(len(l))


### FIXED CODE ###

from bisect import bisect_left
from collections import deque
N = int(input())
d = deque()

for i in range(N):
    a = int(input())
    n = bisect_left(d, a)
    if n != 0:
        d[n-1] = a
    else:
        d.appendleft(a)
print(len(d))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
S = input()

ans = set()

def solve(c, idx):
    if len(c)==3:
        ans.add(c)
        return
    if idx >= len(S):
        return
    solve(c+S[idx], idx+1)
    solve(c, idx+1)

if __name__ == "__main__":
    solve("", 0)
    print(len(ans))

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    cnt = 0
    n = str(i).zfill(3)
    for c in S:
        if c == n[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

print(ans)