Harryxun/stf_run huggingface dataset:
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 
N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans
    
if n==2:
    print(0)
else:
    ans=pow(2,n)-1-comb(n,a,mod)-comb(n,b,mod)
    print(ans%(10**9+7))

### FIXED CODE ###

n,a,b=map(int, input().split())
 
def comb(n, r,MOD):
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return p * pow(q, MOD-2, MOD) % MOD

mod=10**9+7
    
A=comb(n,a,mod)
B=comb(n,b,mod)  
C=pow(2,n,mod)

if n==2:
    print(0)
else:
    print((C-1-A-B)%mod)
#! /usr/bin/python
# -*- coding: utf-8 -*-

(t, n) = map(int, raw_input().split())
while t != 0 or n != 0:
    M = [[False]*100 for i in range(100)]
    for i in range(n):
        (obx, oby) = map(int, raw_input().split())
        M[oby+50][obx+50] = True
    (sx, sy) = map(int, raw_input().split())
    ST = [] #0:y 1:x 2:turn num
    cnt = 0
    #----above init----#
    #print s
    ST.append([sy+50, sx+50, 0])
    while len(ST) > 0:
        y = ST[0][0]
        x = ST[0][1]
        c = ST[0][2]
        ST.pop(0)
        if c <= t and M[y][x] == False:
            M[y][x] = True
            cnt += 1
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dx+dy != 0 and M[y+dy][x+dx] == False:
                        ST.append([y+dy, x+dx, c+1])
    print cnt
    
    (t, n) = map(int, raw_input().split())

### FIXED CODE ###

#! /usr/bin/python
# -*- coding: utf-8 -*-

(t, n) = map(int, raw_input().split())
while t != 0 or n != 0:
    M = [[False]*201 for i in range(201)]
    for i in range(n):
        (obx, oby) = map(int, raw_input().split())
        M[oby+100][obx+100] = True
    (sx, sy) = map(int, raw_input().split())
    ST = [] #0:y 1:x 2:turn num
    cnt = 0
    #----above init----#
    #print s
    ST.append([sy+100, sx+100, 0])
    while len(ST) > 0:
        y = ST[0][0]
        x = ST[0][1]
        c = ST[0][2]
        ST.pop(0)
        if y < 0 or 200 < y or x < 0 or 200 < x:
            continue
        if c <= t and M[y][x] == False:
            M[y][x] = True
            cnt += 1
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dx+dy != 0:
                        ST.append([y+dy, x+dx, c+1])
    print cnt
    
    (t, n) = map(int, raw_input().split())
# WARN: Require mod number m is prime number
class ModComb:
    # For nCr mod m
    def __init__(self, n_max, m):
        self._n_max = n_max
        self._m = m
        self._mod_facts = [1] * (n_max+1)       # list of n! mod m
        self._mod_inv_facts = [1] * (n_max+1)   # list of inverse r! mod m

        if not m >= 3:
            raise ValueError('Require mod number m >= 3')

        # Calc n_max! mod m
        for i in range(2, n_max+1):
            self._mod_facts[i] = self._mod_facts[i-1] * i % m

        # Calc inverse r! mod m
        self._mod_inv_facts[n_max] = pow(self._mod_facts[n_max], m-2, m)
        for i in range(n_max-1, 1, -1):
            self._mod_inv_facts[i] = self._mod_inv_facts[i+1] * (i+1) % m

    def calc(self, n, r):
        # Return nCr mod m
        if n > self._n_max:
            raise Exception('n is larger than n_max')
        if r > n:
            raise Exception('r is larger than n')

        if r == 0:
            return 1

        m = self._m
        return self._mod_facts[n] * self._mod_inv_facts[r] * self._mod_inv_facts[n-r] % m

N, K = map(int, input().split())

MOD = 10**9 + 7

mcomb = ModComb(N, MOD)
for i in range(1, K+1):
    #if N-K < (i-1) :
    #    print(0)
    #    continue
    b = mcomb.calc(K-1, i-1)
    # N-K-(i-1) を i+1に組分け
    p = mcomb.calc(N-K-(i-1) + i, i)
    #print(N-K-(i-1) + i, i)
    #print(b, p)
    print(b*p % MOD)


### FIXED CODE ###

# WARN: Require mod number m is prime number
class ModComb:
    # For nCr mod m
    def __init__(self, n_max, m):
        self._n_max = n_max
        self._m = m
        self._mod_facts = [1] * (n_max+1)       # list of n! mod m
        self._mod_inv_facts = [1] * (n_max+1)   # list of inverse r! mod m

        if not m >= 3:
            raise ValueError('Require mod number m >= 3')

        # Calc n_max! mod m
        for i in range(2, n_max+1):
            self._mod_facts[i] = self._mod_facts[i-1] * i % m

        # Calc inverse r! mod m
        self._mod_inv_facts[n_max] = pow(self._mod_facts[n_max], m-2, m)
        for i in range(n_max-1, 1, -1):
            self._mod_inv_facts[i] = self._mod_inv_facts[i+1] * (i+1) % m

    def calc(self, n, r):
        # Return nCr mod m
        if n > self._n_max:
            raise Exception('n is larger than n_max')

        if r == 0:
            return 1

        m = self._m
        return self._mod_facts[n] * self._mod_inv_facts[r] * self._mod_inv_facts[n-r] % m

N, K = map(int, input().split())

MOD = 10**9 + 7

mcomb = ModComb(N, MOD)
for i in range(1, K+1):
    if N-K < (i-1) :
        print(0)
        continue
    b = mcomb.calc(K-1, i-1)
    # N-K-(i-1) を i+1に組分け
    p = mcomb.calc(N-K-(i-1) + i, i)
    #print(N-K-(i-1) + i, i)
    #print(b, p)
    print(b*p % MOD)
import sys
input = sys.stdin.readline

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

A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

ZERO=1<<(H+W)
DP=[[1<<ZERO for i in range(W)] for i in range(H)]

DP[0][0]=1<<H+W+SA[0][0]

for i in range(H):
    for j in range(W):
        if i+1<H:
            DP[i+1][j]|=DP[i][j]<<SA[i+1][j]
            DP[i+1][j]|=DP[i][j]>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=DP[i][j]<<SA[i][j+1]
            DP[i][j+1]|=DP[i][j]>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*2+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-H-W))

print(ANS)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[0 for i in range(W)] for j in range(H)]

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)
s = list(input())
l = len(s)
if s[0] == 'A':
    c_cnt = 0
    for i, m in enumerate(s):
        if 1<i<l-1 & m=='C':
            cn = i
            c_cnt += 1
    if c_cnt == 1:
        tmp = s
        tmp.pop(0)
        tmp.pop(cn)
        tmp_s = ''.join(tmp)
        if tmp_s == tmp_s.lower():
            print('AC')
else:
    print('WA')



### FIXED CODE ###

s = list(input())
l = len(s)
if s[0] == 'A':
    c_cnt = 0
    cn_l = []
    for i, m in enumerate(s):
        if 1<i<l-1 and m=='C':
            cn_l.append(i)
            c_cnt += 1
    if c_cnt == 1:
        cn = int(cn_l[0])
        tmp = s
        tmp.pop(0)
        tmp.remove('C')
        tmp_s = ''.join(tmp)
        if tmp_s == tmp_s.lower():
            print('AC')
        else:
            print('WA')
    else:
        print('WA')
else:
    print('WA')
a, b, x = list(map(int, input().split()))
A = a // x
B = b // x
c = 0
if a % x == 0:
	c += 1
print(B - A + c)

### FIXED CODE ###

x = input().split()
y = list(x[1])
print("A" + y[0] + "C")
print(2**(len(bin(int(input())))-3)

### FIXED CODE ###

print(2**(len(bin(int(input())))-3))
N=int(input())
m=N[-1]
if m== 2 or m==4 or m==5 or m==7 or m==9:
  print("hon")
elif m==0 or m==1 or m==6 or m==8:
  print("pon")
else
  print("bon"


### FIXED CODE ###

N=input()
m=int(N[-1])
if m== 2 or m==4 or m==5 or m==7 or m==9:
  print("hon")
elif m==0 or m==1 or m==6 or m==8:
  print("pon")
else:
  print("bon")
h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "#":
            if (table[i+1][j]=="#" and table[i][j+1]=="#") or (table[i+1][j]=="." and table[i][j+1]=="."):
                poss = False
for i in range(1, h):
    if table[i][w-1]=="#" and table[i-1][w]=="#":
        poss = False
for i in range(1, w):
    if table[h][i-1]=="#" and table[h-1][i]=="#":
        poss = False

if poss:
    print("Possible")
else:
    print("Impossible")


### FIXED CODE ###

h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "#":
            if (table[i+1][j]=="#" and table[i][j+1]=="#") or (table[i+1][j]=="." and table[i][j+1]=="."):
                poss = False
for i in range(1, h):
    if table[i][w-2]=="#" and table[i-1][w-1]=="#":
        poss = False
for i in range(1, w):
    if table[h-1][i-1]=="#" and table[h-2][i]=="#":
        poss = False

if poss:
    print("Possible")
else:
    print("Impossible")
import math
s, t = input().split()
s = int(s)
t = int(t)
result = s * t // math.gcd(s,t)
print(result)

### FIXED CODE ###

import fractions
s, t = input().split()
s = int(s)
t = int(t)
result = s * t / fractions.gcd(s,t)
print(int(result))
five_dish = [int(input()) for _ in range(5)]
idx = None
maxdiff = 0
result = 0
for i in range(len(five_dish)):
    tmp = five_dish[i] % 10
    if tmp == 0:
        pass
    else:
        if 10 - tmp > maxdiff:
            maxdiff = 10 - tmp
            idx = i
        else:
            pass
for j in range(len(five_dish)):
    if j == idx:
        pass
    else:
        if five_dish[j] % 10 == 0:
            result += five_dish[j]
        else:
            result += five_dish[j] + (10 - (five_dish[j] % 10))
result += five_dish[idx]
print(result)


### FIXED CODE ###

five_dish = [int(input()) for _ in range(5)]
idx = 0
maxdiff = 0
result = 0
for i in range(len(five_dish)):
    tmp = five_dish[i] % 10
    if tmp != 0:
        if 10 - tmp > maxdiff:
            maxdiff = 10 - tmp
            idx = i
for j in range(len(five_dish)):
    if j == idx:
        continue
    else:
        if five_dish[j] % 10 == 0:
            result += five_dish[j]
        else:
            result += five_dish[j] + (10 - (five_dish[j] % 10))
result += five_dish[idx]
print(result)
import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2:
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True

if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")
S, T = map(int, input().split())
A, B = map(int, input().split())
U = int(input())
if (U == T):
  print(str(A)+" "+str(B-1))
else:
  print(str(A-1)+" "+str(B))



### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()
if (U == T):
  print(str(A)+" "+str(B-1))
else:
  print(str(A-1)+" "+str(B))
# この方針かしこい

import os
import sys
import numpy as np

def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = np.zeros_like(S)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, A, B):
    Diff = np.empty(3*N, dtype=np.int64)
    Diff[0] = B[0] ^ B[-1]
    Diff[1:N] = B[1:] ^ B[:-1]
    Diff[N] = Diff[2*N] = A[0] ^ A[-1]
    Diff[N+1:2*N] = Diff[2*N+1:3*N] = A[1:] ^ A[:-1]
    Z = z_algo(Diff)[N:2*N]
    Ans = [(0,0)]*0
    for i in range(N):
        z = Z[i]
        if z >= N:
            Ans.append((i, B[0]^A[i]))
    return np.array(Ans)


# >>> numba compile >>>
numba_config = [
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8[:,:](i8,i8[:],i8[:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    B = np.array(input().split(), dtype=np.int64)
    Ans = solve(N, A, B).tolist()
    print("\n".join(map(lambda x: " ".join(map(str, x)), Ans)))

main()


### FIXED CODE ###

def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = [0] * n
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_diff = []
a2 = A[-1]
for a in A:
    A_diff.append(a^a2)
    a2 = a
B_diff = []
b2 = B[-1]
for b in B:
    B_diff.append(b^b2)
    b2 = b
A_diff_2 = A_diff + A_diff[:-1]
Z = z_algo(A_diff_2)
A_diff_str = "_".join(map(str, A_diff_2))
B_diff_str = "_".join(map(str, B_diff))
idx = A_diff_str.find(B_diff_str)
if idx==-1:
    exit()
idx = A_diff_str[:idx].count("_")
Ans = []
b0 = B[-idx]
for i, (z, a, b) in enumerate(zip(Z, A, B)):
    if z >= N:
        Ans.append([(idx+i)%N, a^b0])
        # x = [idx, i, a, b, B[-idx]]
        # print(x)
Ans.sort()  # これいる？
for k, x in Ans:
    print(f"{k} {x}")
n = int(input())
a = list(map(int,input().split()))
c = 0
for i in range(n):
  if i == a[a[i]]:
    c += 1
print(c//2)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0
for i in range(n):
  if i == a[a[i]-1]-1:
    c += 1
print(c//2)
from math import gcd
from functools import reduce

def lcm(p,q):
    return p*q//gcd(p,q)

N=int(input())
a=list(map(int,input().split(' ')))
m=reduce(lcm,a)-1
result=0
for i in a:
    result+=m%i
print(result)


### FIXED CODE ###

def gcd(m,n):
    while n!=0:
        l=n
        n=m%n
        m=l
    return m

def lcm(p,q):
    return p*q//gcd(p,q)

N=int(input())
a=list(map(int,input().split(' ')))
lcm_=lcm(a[0],a[1])
for i in range(2,len(a)):
    lcm_=lcm(lcm_,a[i])
result=0
m=lcm_-1
for i in a:
    result+=m%i
print(result)
n=int(input())
arr=list(map(int,input().split()))
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
acum=[arr[0]]
for i in range(1,n+1):
  acum.append(acum[-1]+arr[i])
b=[0]*n
b[0]=1-arr[0]
b[0]=min(b[0],acum[n]-b[0])
for i in range(1,n):
  b[i]=2*b[i-1]-arr[i]
  b[i]=min(b[i],acum[n]-acum[i])
for i in range(n):
  if b[i]<=0:
    print(-1)
    exit()
ans=sum(arr)+sum(b)
print(ans)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
  exit()
for i in range(n):
  if i<=30 and arr[i]>=2**i:
    print(-1)
    exit()
if n<=30 and arr[n]>2**n:
  print(-1)
  exit()
maxs=[0]*(n+1)
maxs[0]=1
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
tmp=arr[n]
for i in range(n-1,-1,-1):
  maxs[i]=min(maxs[i],tmp)
  tmp+=arr[i]
mins=[0]*(n+1)
for i in range(n-1,-1,-1):
  mins[i]=(mins[i+1]+arr[i+1]+1)//2
for i in range(n):
  if maxs[i]<mins[i]:
    print(-1)
    exit()
ans+=sum(maxs)
print(ans)
import math

def lcm(x,y):
    return (x*y) // math.gcd(x, y)
    
x, y = map(int, input().split())
s = input()
t = input()

check = [""] * (10**6)
lc = lcm(x,y)

s_l = lc//x
t_l = lc//y

for i in range(x):
    check[i*s_l + 1] = s[i]
    
for i in range(y):
    if check[i*t_l + 1] != t[i] and check[i*t_l + 1] != "":
        print(-1)
        break
else:
    print(lc)



### FIXED CODE ###

import fractions

def lcm(x,y):
    return (x*y) // fractions.gcd(x, y)
    
x, y = map(int, input().split())
s = input()
t = input()

lc = lcm(x,y)

s_l = lc//x
t_l = lc//y

for i in range(y):
    if i%s_l == 0:
        if t[i] == s[i*t_l//s_l]:
            continue
        else:
            print(-1)
            break
else:
    print(lc)
N = int(input()) 
A = list(map(int,input().split()))
c = 1
i = 0
for i in N-1:
    if c *= A[i] >= 10**18:
      print(-1)
  
print(c)



### FIXED CODE ###

n=int(input())
ls=[int(s) for s in input().split(" ")]

if 0 in ls:
  print(0)
else:
  num=1
  for i in ls:
    num*=i
    if num>10**18:
      num=-1
      break

  print(num)
a, b = map(int, input().split())

print(mean(a, b).roundup())

### FIXED CODE ###

import math

a, b = map(int, input().split())
c = (a + b) / 2
print(math.ceil(c))
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def solve(W, N, v):
    cache = [[None for _ in range(W + 1)] for _ in range(N)]
    def loop(i, w):
        if i == N:
            return (0, 0)
        if cache[i][w] is not None:
            return cache[i][w]
        cache[i][w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i][w] = max(cache[i][w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i][w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve(W, N, v)
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

### FIXED CODE ###

import itertools

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    d = [tuple(map(int, input().split(','))) for _ in range(N)]

    v = [0 for _ in range(W + 1)]
    for i in range(N):
        for j in range(W, d[i][1] - 1, -1):
            v[j] = max(v[j], v[j - d[i][1]] + d[i][0])
    print("Case %d:\n%d\n%d" % (dn, max(v), v.index(max(v))))
N=int(input())
ba=bx=xa=0
ans=0
for i in range(N):
    s=input()
    ans+=s.count('AB')
    if s.startswith('B') and s.endswith('A'):
        ba+=1
    elif s.startswith('B'):
        bx+=1
    elif s.endswith('A'):
        xa+=1

if ba==0:
    ans+=min(bx,xa)
elif ba>0:
    if bx+xa>0:
        ans+=ba+min(bx,xa)
    else bx+xa==0
        ans+=ba-1

print(ans)

### FIXED CODE ###

N=int(input())
ba=bx=xa=0
ans=0
for i in range(N):
    s=input()
    ans+=s.count('AB')
    if s.startswith('B') and s.endswith('A'):
        ba+=1
    elif s.startswith('B'):
        bx+=1
    elif s.endswith('A'):
        xa+=1

if ba==0:
    ans+=min(bx,xa)
elif ba>0:
    if bx+xa>0:
        ans+=ba+min(bx,xa)
    elif bx+xa==0:
        ans+=ba-1

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

for i in range(a, b):
    if i%c != 0:
        if i%d !=0:
            print(i)

### FIXED CODE ###

count=0

security=input()
sec_list=list(security)

for s in range(0,len(security)-1):
    if sec_list[s]==sec_list[s+1]:
        count+=1

if count != 0:
    print("Bad")
else:
    print("Good")
import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
N = int(input())
h = np.array(list(map(int, input().split())))

#@njit
def solve(N,h,s):
    if (np.all(h <= 0)):
        return s
    else:
        w = np.where(h > 0)[0]
        try:
            l = w[0]
            r = w[0]
            i = 1
            while (i < len(w)):
                if (w[i] == r + 1):
                    r = w[i]
                i += 1
        except Exception as e:
            return s
        cat = np.concatenate([h[:l], h[l:r+1]-1, h[r+1:]])
        return solve(N, cat, s+1)

print(solve(N,h,0))


### FIXED CODE ###

import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
N = int(input())
h = np.array(list(map(int, input().split())))

#@njit

def solve(N,h):
    s = 0
    while (np.any(h > 0)):
        w = np.where(h > 0)[0]
        l = w[0]
        r = w[0]
        i = 1
        while (i < len(w)):
            if (w[i] == r + 1):
                r = w[i]
            i += 1
        
        h = np.concatenate([h[:l], h[l:r+1]-1, h[r+1:]])
        s += 1
    return s

print(solve(N,h))