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

S=list(input())

count=0
# print(S)

bExists = True

while(bExists):
	bExists = False
	for n in range(len(S)-1):
		# 最初に見つかったものから抜いていく
		if S[n] != S[n+1]:
			del S[n:n+2]
			# print(S)
			count += 2
			bExists = True
			break


print(count)


### FIXED CODE ###

S=input()

count0=0
count1=0
# print(S)

for s in S:
	if s == '0':
		count0 += 1
	else:
		count1 += 1

print(min(count0,count1) * 2)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
t = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            t += gcd(i,j,l)
print(t)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
t = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if math.gcd(i,j) ==1:
            t += 1*len(list(range(1,k+1)))
        else:
            for l in range(1,k+1):
                    t += gcd(i,j,l)
print(t)
### BUGGY CODE ###

import sys
from sys import stdin
N = int(stdin.readline().rstrip())
print(0)
s = input()
cnt = 0
N = (N-1)//2
if s == "Male":
    for _ in range(25):
        print(N)
        #sys.stdout.write(N)
        sys.stdout.flush()
        s = input()
        if s == "Male" and N % 2 == 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Female" and N % 2 != 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max(min(N//2,(L-N)//2),1)
        
elif s == "Female":
    for _ in range(25):
        print(N)
        #sys.stdout.write(N)
        sys.stdout.flush()
        s = input()
        if s == "Female" and N % 2 == 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Male" and N % 2 != 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max(min(N//2,(L-N)//2),1)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
r = N-1
l = 0
print(0)
s = input()
cnt = 0
mid = (r+l)//2
if s == "Male":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Male" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Female" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
        
elif s == "Female":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Female" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Male" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
### BUGGY CODE ###

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

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        for r in range(l+1, N+1):
            for d in range(1, N+1):
                for u in range(d+1, N+1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        no_three = True
        for r in range(N, l, -1):
            no_two = True
            for d in range(1, N+1):
                no_one = True
                for u in range(d+1, N+1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
                        no_one = False
                        break
                if no_one:
                    break
                else:
                    no_two = False
            if no_two:
                break
            else:
                no_three = False
        if no_three:
            break
                

    print(ans)

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

from itertools import accumulate
n=int(input())
acc=[0]+list(accumulate(map(int,input().split())))
dp=[[0]*(n+1) for _ in range(n)]
for w in range(2,n+1):
    for l in range(n-w+1):
        r=l+w
        dp[l][r]=min(dp[l][m]+dp[m][r] for m in range(l+1,r))+acc[r]-acc[l]
print(dp[0][n])

### FIXED CODE ###

from itertools import accumulate
 
n = int(input())
acc = [0] + list(accumulate(map(int, input().split())))
dp = [[0] * (n + 1) for _ in range(n)]
for w in range(2, n + 1):
    for l in range(n - w + 1):
        r = l + w
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + acc[r] - acc[l]
print(dp[0][n])
### BUGGY CODE ###

n=int(input())
Rt=[]
for i in range(n):
	Rt.append(int(input()))

a=-999999999
for i in range(n):
	for j in range(i+1,n):
		if a<Rt[j]-Rt[i]:
			a=Rt[j]-Rt[i]
		
print(a)


### FIXED CODE ###

n=int(input())
Rt=[]
for i in range(n):
	Rt.append(int(input()))

maxv=Rt[1]-Rt[0]
minv=Rt[0]
for j in range(1,n):
	maxv=max(maxv,Rt[j]-minv)
	minv=min(minv,Rt[j])
		
print(maxv)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''

    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    queries.sort(key=lambda x:x[0])

    que = []
    cnt = 0
    for num, val in queries:
        que += [num]*val
        cnt += val
        if cnt >= K:
            break

    print(que[K-1])

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    queries.sort(key=lambda x:x[0])

    temp_que = []
    for num, val in queries:
        temp_que = num
        K -= val
        if K <= 0:
            break

    print(temp_que)

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

nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
sumlist.sort(reverse=True)
print(sumlist[0])


### FIXED CODE ###

nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[]
for i in range(Q):
    tp=tuple(map(int, input().split()))
    ablist.append(tp)
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools
case=list(itertools.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        if nowcase[ablist[i][1]-1]-nowcase[ablist[i][0]-1]==ablist[i][2]:
            sumd+=ablist[i][3]
    sumlist.append(sumd)
print(max(sumlist))
### BUGGY CODE ###

import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    _next = set()
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 1:
                battle_dict[i].pop(0)
            else:
                battle_dict[i].pop(0)
                battle_dict.pop(i)
            if len(battle_dict[j]) > 1:
                battle_dict[j].pop(0)
            else:
                battle_dict[j].pop(0)
                battle_dict.pop(j)
            _next.update(v)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        new = tuple(sorted([i, j[0]]))
        if i in _next or j[0] in _next:
           cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    c = list(map(str, input().split()))
    if c[0] == '1':
        s = s[::-1]
    if c[0] == '2':
        if c[1] == '1':
            s = c[2] + s
        if c[1] == '2':
            s = s + c[2]

print(s)

### FIXED CODE ###

s=input()
q=int(input())
f=""
b=""
r=0
for i in range(q):
  query=input().split()
  if int(query[0])==1:
    r=1-r
  else:
    if (r^(int(query[1])-1))==0:
      f+=query[2]
    else:
      b+=query[2]
ret=f[::-1]+s+b
if r:
  ret=ret[::-1]
print(ret)
### BUGGY CODE ###

N = int(input())

cnt=0
for n in range(1,N+1):
  item_cnt=0
  num_digit =len(str(n))
  chk_n = n
  chk_7 = 0
  chk_5 = 0
  chk_3 = 0
  for i in range(num_digit):
    a = chk_n % 10
    chk_n = chk_n // 10
    if a == 7:
      chk_7 += 1
      item_cnt += 1
      if item_cnt == num_digit and chk_7 > 0 and chk_5 > 0 and chk_3 >0:
        cnt +=1
        #print(n)
        break
    elif a== 5:
      chk_5 += 1
      item_cnt += 1
      if item_cnt == num_digit and chk_7 > 0 and chk_5 > 0 and chk_3 >0:
        cnt +=1
        #print(n)
        break
    elif a == 3:
      chk_3 += 1
      item_cnt += 1
      if item_cnt == num_digit and chk_7 > 0 and chk_5 > 0 and chk_3 >0:
        cnt +=1
        #print(n)
        break      
   
    else:
      break
print(cnt)

### FIXED CODE ###

N = int(input())

def calculate(s):
  if len(s) > 1:
    if int(s) > N:
      return 0
  
  ret = 1 if all([s.count(c) for c in '753']) else 0
  
  for i in '753':
    ret +=calculate(s+i)
  return ret

print(calculate(''))
### BUGGY CODE ###

K=int(input())
S=input()
N=len(S)
p=10**9+7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N+K ):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# ②事前計算した項を掛け合わせ
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] * factinv[r] * factinv[n-r]) % p



A=0
TF=[1]
TS=[1]
for i in range(K+1):
    TF.append(TF[i]*25 %p)
    TS.append(TS[i]*26 %p)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*cmb(i+N-1,i,p)) %p
print(A)

### FIXED CODE ###

K=int(input())
S=input()
N=len(S)
p=10**9+7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N+K ):
    fact.append((fact[-1] * i) % p) # [-1]は後ろから?
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] * factinv[r] * factinv[n-r]) % p
A=0
TF=[1]
TS=[1]
for i in range(K+1):
    TF.append(TF[i]*25 %p)
    TS.append(TS[i]*26 %p)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*cmb(i+N-1,i,p)) %p
print(A)
### BUGGY CODE ###

s=input()
n=len(s)
si=int(s)
mod=2019
t={}
t[si%mod]=1
for i in range(n):
    si-=int(s[i])*pow(10,n-1-i,mod)
    a=si%mod
    if a in t:
        t[a]+=1
    else:
        t[a]=1
ans=0
for v in t.values():
    ans+=(v*(v-1))//2
print(ans)


### FIXED CODE ###

s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)
### BUGGY CODE ###


h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)


### FIXED CODE ###

h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)
### BUGGY CODE ###

# s1 = input()
# len_s = len(s1)
# s2 = s1
# while True:
#     len_1 = len(s2)
#     s2 = s2.replace("01", "").replace("10", "")
#     len_2 = len(s2)
#     if len_1 == len_2:
#         break
#
# print(len_s - len(s2))

s = input()
s2 = s
# for i in range(len(s) // 2, 0, -1):
#     # print("i", i)
#     # print("s2", s2)
#     m1 = "1" * i + "0" * i
#     m2 = "0" * i + "1" * i
#     s2 = s2.replace(m1, "").replace(m2, "")

while True:
    len_1 = len(s2)
    s2 = s2.replace("0000011111", "").replace("1111100000", "")
    s2 = s2.replace("01", "").replace("10", "")
    len_2 = len(s2)
    if len_1 == len_2:
        break
print(len(s) - len(s2))


### FIXED CODE ###

s = input()
ans = min(s.count('0'), s.count('1'))
print(ans * 2)
### BUGGY CODE ###

from math import floor
A,B,N=list(map(int,input().split()))
ans = 0
for x in range(N+1):
  a = floor(A*x/B)-A*floor(x/B)
  if ans < a:
    ans = a
  if B<x:
    break
print(ans)

### FIXED CODE ###

from math import floor
A,B,N=list(map(int,input().split()))
x=min((B-1),N)
ans=floor(A*x/B)-A*floor(x/B)
print(ans)
### BUGGY CODE ###

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

x = N

while True:
  if abs(x-K) < x:
  	x = abs(x-K)
  else:
    break
print(x)

### FIXED CODE ###

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

a = N//K
b = abs(N-(a+1)*K)

if N - a*K <= b:
  print(N-a*K)
elif N - a*K > b:
  print(b)
### BUGGY CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
#一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
        # print(i, j, a, b, dp)
print(dp[-1])

### FIXED CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        m += S[i]=='M'
        c += S[i]=='C'
        a += m*(S[i]=='C')
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            m += S[i+k-1]=='M'
            c += S[i+k-1]=='C'
            a += m*(S[i+k-1]=='C')
        m -= S[i-1]=='M'
        a -= c*(S[i-1]=='M')
        c -= S[i-1]=='C'
        b += a*(S[i]=='D')
        if S[i]=='D' and i==e:
            break
    ans.append(b)
printrows(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a += m
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a += m
        if S[i-1]=='M':
            m -= 1
            a -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            b += a
            if i==e:
                break
    ans.append(b)
printrows(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
mod = 998244353

FACT=[1]
for i in range(1,25*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(25*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
mod = 998244353

FACT=[1]
for i in range(1,4*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(4*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)
### BUGGY CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
low = -1

for i in range(N):
    low = Ps[i]

    for j in range(i):
        if (low > Ps[j]):
            break
        if (j == i-1):
            count += 1

print(count+1)

### FIXED CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
min = Ps[0]+1

for i in range(N):
    if (Ps[i] < min):
        min = Ps[i]
        count += 1

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

import io
import os

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

R, C, K = [int(x) for x in input().split()]
grid = [[0 for c in range(C)] for r in range(R)]
for r, c, v in ((int(x) for x in input().split()) for i in range(K)):
    grid[r - 1][c - 1] = v


dp = [[[0 for i in range(3 + 1)] for c in range(C + 1)] for r in range(R + 1)]
dp2 = [[0 for c in range(C + 1)] for r in range(R + 1)]
for r in range(R):
    for c in range(C):
        for numTakenThisRow in range(3 + 1):
            best = dp[r][c - 1][numTakenThisRow]  # came from left
            if not numTakenThisRow:
                # came from top, didn't take curr
                best = max(best, dp2[r - 1][c])
            else:
                # came from left, took curr
                best = max(best, dp[r][c - 1][numTakenThisRow - 1] + grid[r][c])
                # came from top, took curr
                if numTakenThisRow == 1:
                    best = max(best, dp2[r - 1][c] + grid[r][c])
            dp[r][c][numTakenThisRow] = best
        dp2[r][c] = max(dp[r][c][i] for i in range(3 + 1))
print(dp2[R - 1][C - 1])


### FIXED CODE ###

import io
import os
from collections import defaultdict

DEBUG = False
if not DEBUG:

    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    R, C, K = [int(x) for x in input().split()]
    grid = [[0 for c in range(C)] for r in range(R)]
    for r, c, v in ((int(x) for x in input().split()) for i in range(K)):
        grid[r - 1][c - 1] = v
else:
    import random

    random.seed(0)
    R, C = 3000, 3000
    # 2 * 10**5 / 90 * 10**5 full
    grid = [
        [int(random.randint(1, 90) <= 2) * random.randint(0, 10 ** 9) for c in range(C)]
        for r in range(R)
    ]
    print(sum(bool(grid[r][c]) for r in range(R) for c in range(C)))
    print("done gen")

    from timeit import default_timer as timer

    startTime = timer()


currRow = [[0 for i in range(3 + 1)] for c in range(C + 1)]
prevRow = [0 for c in range(C + 1)]
nextPrevRow = [0 for c in range(C + 1)]

inf = float("inf")
for r in range(R):
    for c in range(C):
        for numTakenThisRow in range(3 + 1):
            best = max(
                currRow[c - 1][numTakenThisRow],  # came from left
                prevRow[c],  # came from top, didn't take curr
                currRow[c - 1][numTakenThisRow - 1] + grid[r][c]
                if numTakenThisRow
                else 0,  # came from left, took curr
                prevRow[c] + grid[r][c]
                if numTakenThisRow == 1
                else 0,  # came from top, took curr
            )
            currRow[c][numTakenThisRow] = best
        nextPrevRow[c] = max(currRow[c][i] for i in range(3 + 1))
    prevRow, nextPrevRow = nextPrevRow, prevRow
print(prevRow[C - 1])

if DEBUG:
    print(timer() - startTime)