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

N, a, b = map(int, input().split())
 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7 #出力の制限
X = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, X + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
ax = cmb(N, a, mod)
bx = cmb(N, b, mod)
 
print((pow(2, N) - ax - bx - 1)%mod)

### FIXED CODE ###

N, a, b = map(int, input().split())

MOD = 10**9+7

def modcmb(n, r, m):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    return y * pow(x, m-2, m) % m

ans = pow(2, N, MOD) - modcmb(N, a, MOD) - modcmb(N, b, MOD) - 1
print(ans % MOD)
### BUGGY CODE ###

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    if 1 in temp or N in temp:
        a.append(min(temp))
        b.append(max(temp))

M = len(a)

flag = False

index_1 = [i for i, x in enumerate(a) if x == 1]

for i in index_1:
    for j in range(M):
        if i != j and b[i] == a[j] and N == b[j]:
            print('POSSIBLE')
            flag = True
            break
if not flag:
    print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    if 1 == temp[0]:
        a.append(temp[1])
    elif N == temp[1]:
        b.append(temp[0])

if any(list(set(a) & set(b))):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[i] for i in range(N)]  # 各頂点の持つ部分木の頂点の集合
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = np.zeros(N, dtype=np.int32)

for a, b in edges[::-1]:
    children[a-1] += children[b-1]

children = [list(set(child)) for child in children]

for _ in range(Q):
    p, x = map(int, input().split())
    counts[children[p-1]] += x

print(' '.join(list(map(str, counts))))

### FIXED CODE ###

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

def main():
    N, Q = map(int, input().split())
    # edges = [None]*N
    edges = [[] for _ in range(N)]
    # edges[0] = 0
    # edges[0].append = 0
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[b-1].append(a-1)
        edges[a-1].append(b-1)

    counts = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        counts[p-1] += x

    parent_nodes = deque()
    parent_nodes.append(0)
    visited_nodes = set()
    while parent_nodes:
        parent = parent_nodes.popleft()
        if parent in visited_nodes:
            continue
        visited_nodes.add(parent)
        for child in edges[parent]:
            if child in visited_nodes:
                continue
            counts[child] += counts[parent]
            parent_nodes.append(child)

    print(' '.join(list(map(str, counts))))

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

import math

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

min_ind = a.index(min(a))

start = sorted([min_ind - x for x in range(k) if min_ind - x >= 0])
end = [s+k-1 for s in start]

ans = 10**6
for s, e in zip(start, end):
    ans = min(ans, math.ceil(len(a[:s])/(k-1)) + math.ceil(len(a[e+1:])/(k-1)))

print(ans+1)


### FIXED CODE ###

import math

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    min_ind = a.index(min(a))

    start = [min_ind - x for x in range(k) if min_ind - x >= 0]
    end = [s+k-1 for s in start]

    ans = 10**6
    for s, e in zip(start, end):
        ans = min(ans, math.ceil(s/(k-1)) + math.ceil((n-(e+1))/(k-1)))

    print(ans+1)

main()
### BUGGY CODE ###

n, m = [int(x) for x in raw_input().split()]
a = map(int, raw_input().split())
a.sort()
bc = []
for _ in xrange(m):
    bc.append([int(x) for x in raw_input().split()][::-1])
bc.sort(reverse=True)
for i in xrange(n):
    if len(bc) == 0:
        break
    if bc[0][1] == 0:
        bc = bc[1:]
    if len(bc) == 0:
        break
    if a[i] < bc[0][0]:
        a[i] = bc[0][0]
        bc[0][1] -= 1
    else:
        bc = bc[1:]
print sum(a)


### FIXED CODE ###

n, m = [int(x) for x in raw_input().split()]
a = map(int, raw_input().split())
a.sort()
bc = []
for _ in xrange(m):
    bc.append([int(x) for x in raw_input().split()][::-1])
bc.sort(reverse=True)
j = 0
for i in xrange(n):
    if j == m:
        break
    if bc[j][1] == 0:
        j += 1
    if j == m:
        break
    if a[i] < bc[j][0]:
        a[i] = bc[j][0]
        bc[j][1] -= 1
    else:
        break
print sum(a)
### BUGGY CODE ###

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

ans = 0

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

print(ans)

### FIXED CODE ###

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

B = {}
B[0] = 1

s = 0
ans = 0

for a in A:
    s += a
    ans += B.get(s,0)
    B[s] = B.get(s,0)+1

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

H, W = map(int, input().split())
a = [input() for _ in range(H)]

white_set = set()
for r in range(H):
    for c in range(W):
        if a[r][c] == '.':
            white_set.add((r, c))

ans = 0
while white_set:
    # print(white_set)
    to_del_set = set()
    for r, c in white_set:
        for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
            nr = r + dr
            if not(0<= nr < H):continue
            nc = c + dc
            if not (0 <= nc < W): continue
            if (nr, nc) not in white_set:
                # 隣接は黒
                to_del_set.add((r, c))
                break
    white_set -= to_del_set
    ans += 1

print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r][c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)
### BUGGY CODE ###

from sys import stdin
n = input().split(' ')
c = 0
K = n[0]
S = n[1]
for i in range(int(K)+1):
    for j in range(int(K)+1):
        for k in range(int(K)+1):
            sum=i+j+k
            if sum is int(S):
                c += 1
                
print(c)

### FIXED CODE ###

k, s = list(map(lambda x: int(x), input().split()))

count = 0
for x in range(k+1):
    for y in range(k+1):
        if x+y+k >= s and x+y <= s:
            count += 1

print(count)
### BUGGY CODE ###

import copy
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

cp = copy.copy(ab)

cp = sorted(cp, key=lambda x: x[1])

cost = [[] for _ in range(n+1)]

for i,j in cp:
    cost[i].append(j)

for i,j in ab:
    ID = cost[i].index(j)+1
    i = str(i)
    i = (6-len(i))*'0'+i
    ID = str(ID)
    ID = (6-len(ID))*'0'+ID
    print(i+ID)

### FIXED CODE ###

n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):
 
        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)
 
 
for i, tmp in enumerate(py):
    print(ans[tmp])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

N,X,Y=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,last,turn) in memo:
        return memo[(n,last,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min ( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,last,turn)]=ret
    return ret


print func(N,Y,0)

### FIXED CODE ###

N,Z,W=map(int,raw_input().split())
a=[]
a=map(int,raw_input().split())

if len(a)!=1:
	print max ( abs(a[-1]-W), abs(a[-2]-a[-1]) )
else:
	print abs(a[0]-W)
### BUGGY CODE ###

# 初期入力
A,B = (int(x) for x in input().split())

#公約数を求める
def kouyakusu(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

#約数 #商と割る数をタプルで返す
def yakusu_tapulu(n):# 商と割る数 両方を返す
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            syou,amari =divmod(n,i)
            divisors.append((syou,i))
    return divisors

#公約数の約数をタプルで作る。互いに素だから要素数は「１」
x_yakusu =[]
x_kouyaku = kouyakusu(A,B) #公約数のリスト
x_yakusu =[yakusu_tapulu(i) for i in x_kouyaku  if len(yakusu_tapulu(i)) ==1]
print(len(x_yakusu))

### FIXED CODE ###

# 初期入力
A,B = (int(x) for x in input().split())

#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf
# 入力値A,Bを素因数分解
A_soinsu =soinsu_bunkai(A)
B_soinsu =soinsu_bunkai(B)

#共通の素数を探す
kyotu_soinsu ={}
a_sosu ={i for i in A_soinsu.keys()}
b_sosu ={i for i in B_soinsu.keys()}
kotae = a_sosu & b_sosu

print(len(kotae)+1) # 素数「１」を足す
### BUGGY CODE ###

from bisect import bisect_left, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                if li >= len(abc[i]):
                    continue
                if abc[i][li] <= r:
                    cnt += 1

            print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            if let == c:
                continue

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                if li >= len(abc[i]):
                    continue
                if abc[i][li] <= r:
                    cnt += 1

            print(cnt)


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

import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

hoge=int(s**0.5)

import math
def isPrime(num):
    if num < 2: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    return True
def callIsPrime(input_num):
    numbers = []
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)
    return numbers
test=(callIsPrime(10**8))

for i in test:
    ss=i
    #print(ss)
    if s%ss==0 and s//ss<=10**9:
        print(0,0,ss,0,0,s//ss)
        exit()



### FIXED CODE ###

import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

y=(-1*s//(10**9))*(-1)
x=10**9*y-s

print(0,0,10**9,1,x,y)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = collections.deque()

ans = 0

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]


def bfs(y, x, cnt):

    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '.'):
        return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and a[y+ddy][x+ddx] == '.'):
            a[y+ddy][x+ddx] = '#'
            queue.append([y + ddy, x+ddx, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            queue.append([i, j, 0])

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
ls = map(int, input().split())
ls = list(ls)


counter = 0
for i, l1 in enumerate(ls):
    j = i+1
    for l2 in ls[i+1:]:
        for l3 in ls[j+1:]:
            if l1 < l2 + l3 and l2 < l1 + l3 and l3 < l2 + l1:
                counter += 1
        j += 1

print(counter)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
ls = map(int, input().split())
ls = sorted(ls)

counter = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        counter += (bisect_left(ls, ls[i] + ls[j]) - 1) - j

print(counter)
### BUGGY CODE ###

import math
from functools import reduce
from itertools import product
 
x = int(input())
print(sum([reduce(math.gcd, i) for i in product(range(1, x+1), repeat=3)]))

### FIXED CODE ###

import math
from itertools import product
 
x = int(input())

s = 0
for a, b, c in product(range(1, x+1), repeat=3):
  s += math.gcd(math.gcd(a, b), c)
print(s)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
aa = list(set(a))
ans = 0

for i in aa:
	if i == 1:
		ans += a.count(i)-1
	else:
		ans += a.count(i)%i
print(ans)

### FIXED CODE ###

#Counterめちゃべんり！！ 辞書型のkey(),value(),items()をつかえるようにしよう
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
aa = Counter(a)

ans = 0
for i,j in aa.items():
	if i > j:
		ans += j
	elif i < j:
		ans += j-i
print(ans)
### BUGGY CODE ###

N = int(input())
S = input().split()
ans = 1
#float
for i in range(N):
    A = int(S[i])
    ans *= A
if ans>1000000000000000000:
    ans = -1
print (ans)

### FIXED CODE ###

N = int(input())
S = input().split()
S.sort()
ans = 1
#float
for i in range(N):
    A = int(S[i])
    if(A==0):
        ans = 0
        break
    else:
        ans *= A
    if ans>1000000000000000000:
        ans = -1
        break
print (ans)
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N = int(input())
    H = np.array(input().split(), np.int64)
    A = np.arange(1,N+1)
    B = np.arange(1,N+1)
    A = A + H
    B = B - H
    ans = 0
    for i in range(1,N):
        ans += N - i - np.count_nonzero(B[i:] - A[:-i])
    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    L = defaultdict(int)
    R = defaultdict(int)
    for i in range(N):
        L[i+1+A[i]] += 1
        R[i+1-A[i]] += 1
    ans = 0
    for key, value in L.items():
        ans += value*R[key]
    print(ans)


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

import sys
sys.setrecursionlimit(10**9)

BLK = 1
WHT = 0
MOD = 10 ** 9 + 7


def calcdp(r, p, bw):
    if dp[r][bw] != -1:
        return dp[r][bw]

    if p == 0:
        cs = H[r]
    else:
        cs = H[r] - {p}

    if len(cs) == 0:
        dp[r][bw] = 1
        return 1
    else:
        if bw == BLK:
            res = 1
            for c in cs:
                res = (res * calcdp(c, r, WHT)) % MOD
            dp[r][BLK] = res
            return res
        else:
            res = 1
            for c in cs:
                res = (res * (calcdp(c, r, WHT) + calcdp(c, r, BLK))) % MOD
            dp[r][WHT] = res

            return res


N = int(input())
H = [set() for _ in range(N + 1)]
for _ in range(1, N):
    x, y = map(int, input().split())
    H[x].add(y)
    H[y].add(x)

dp = [[-1] * 2 for _ in range(N + 1)]

print((calcdp(1, 0, BLK) + calcdp(1, 0, WHT)) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
 
BLK = 1
WHT = 0
MOD = 10 ** 9 + 7
 
 
def calcdp(r, p, bw):
    if dp[r][bw] != -1:
        return dp[r][bw]
 
    if p == 0:
        cs = H[r]
    else:
        cs = H[r] - {p}
 
    if len(cs) == 0:
        dp[r][bw] = 1
        return 1
    else:
        if bw == BLK:
            res = 1
            for c in cs:
                res = (res * calcdp(c, r, WHT)) % MOD
            dp[r][BLK] = res
            return res
        else:
            res = 1
            for c in cs:
                res = (res * (calcdp(c, r, WHT) + calcdp(c, r, BLK))) % MOD
            dp[r][WHT] = res
 
            return res
 
 
N = int(input())
H = [set() for _ in range(N + 1)]
for _ in range(1, N):
    x, y = map(int, input().split())
    H[x].add(y)
    H[y].add(x)
 
dp = [[-1] * 2 for _ in range(N + 1)]
 
print((calcdp(1, 0, BLK) + calcdp(1, 0, WHT)) % MOD)
### BUGGY CODE ###

import sys
s = sys.stdin.readline()
s = s[:-1]
q = int(input())

rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = ~rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            s = s + ci
        else:
            s = ci + s

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

### FIXED CODE ###

import sys
s = sys.stdin.readline()
s = s[:-1]
q = int(input())

front = ''
back = ''
rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = not rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            back += ci
        else:
            front += ci

if rv:
    s = back[::-1] + s[::-1] + front
else:
    s = front[::-1] + s + back
print(s)
### BUGGY CODE ###

import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

l1 = [i for i, x in enumerate(Bh) if x == max(Bh)]
l2 = [j for j, x in enumerate(Bw) if x == max(Bw)]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(max(Bh)+max(Bw)-1)
    exit()
print(max(Bh)+max(Bw))


### FIXED CODE ###

import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)
### BUGGY CODE ###

# D - RGB Triplets

n = int(input())
s = str(input())

R = [i for i, x in enumerate(s) if x=='R']
G = [i for i, x in enumerate(s) if x=='G']
B = [i for i, x in enumerate(s) if x=='B']

ans = 0
for r in R:
    for g in G:
        for b in B:
            tmp = [r, g, b]
            tmp.sort()
            if (tmp[1]-tmp[0])==(tmp[2]-tmp[1]):
                continue
            else:
                ans += 1

print(ans)

### FIXED CODE ###

# D - RGB Triplets

n = int(input())
s = str(input())

r = len([i for i, x in enumerate(s) if x=='R'])
g = len([i for i, x in enumerate(s) if x=='G'])
b = len([i for i, x in enumerate(s) if x=='B'])

ans = r * g * b

for i in range(n):
    for j in range(i+1, n):
        k = j+j-i
        if k >= n:
            break
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans -= 1

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

import math
N = int(input())


def divisors(n):
    ret = set()
    for i in range(1, math.ceil(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                ret.add(i)
            ret.add(n // i)
    return ret


s = divisors(N)
ans = divisors(N-1)

for x in s:
    n = N
    while(n % x == 0):
        n = n // x
    if n % x == 1:
        ans.add(x)

print(len(ans))


### FIXED CODE ###

def divisors(n):
    ret = set()
    for i in range(1, int(n**0.5)+2):
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
    ret.remove(1)
    return ret


def main():
    N = int(input())
    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        if x == 1:
            continue
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)
    print(len(ans))


main()
### BUGGY CODE ###

n,m=map(int,input().split())
s=input()
for i in range(m):
  a,b=map(int,input().split())
  lan=s[a-1:b]
  print(lan.count("AC"))


### FIXED CODE ###

n,m=map(int,input().split())
s=input()
ACsuu=[0 for i in range(n)]
for i in range(1,n):
  ACsuu[i]=ACsuu[i-1]+(1 if s[i-1:i+1]=="AC" else 0)
for i in range(m):
  a,b=map(int,input().split())
  print(ACsuu[b-1]-ACsuu[a-1])
### BUGGY CODE ###

N = int(input())
S = input()
min_num = 10**6
west_num = [0]
east_num = [0]

for i in range(0, N): #累積和を求める.
    if S[i] == 'W':
        west_num.append(1 + max(west_num))
        east_num.append(max(east_num))
    else:
        west_num.append(max(west_num))
        east_num.append(1 + max(east_num))

for i in range(0, N):
    num = 0
    num = west_num[i] + east_num[-1] - east_num[i]
    if num < min_num:
        min_num = num
        
print(min_num)

### FIXED CODE ###

N = int(input())
S = input()
min_num = 10**7
west_num = [0]
east_num = [0]
w_max = 0
e_max = 0
for i in range(0, N): #累積和を求める.
    if S[i] == 'W':
        w_max += 1
    else:
        e_max += 1
        
    west_num.append(w_max)
    east_num.append(e_max)

for i in range(0, N):
    num = west_num[i] + east_num[-1] - east_num[i+1]
    if num < min_num:
        min_num = num
        
print(min_num)