Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(pow(10,9))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.find(self.root[x])
    def union(self,x,y):
        x,y = self.find(x),self.find(y)
        if self.rank[x]<self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.root[y] = x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(pow(10,9))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.find(self.root[x])
    def union(self,x,y):
        x,y = self.find(x),self.find(y)
        if x == y:return
        if self.rank[x]<self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.root[y] = x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)
import numpy as np
L=np.array(map(int,input()))
N=L(0,0)
D=L(0,1)
cnt=0
for idx in range(1,N):
  if L(idx,0)**2+L(idx,1)**2<=D**2:
    cnt=cnt+1
print(cnt)
  

### FIXED CODE ###

N,D=map(int,input().split())
cnt=0
for idx in range(N):
  X,Y=map(int,input().split())
  if X**2+Y**2<=D**2:
    cnt=cnt+1
print(cnt)
N,Y=map(int,input().split())
ichiman=0
gosen=0
sen=0
se_ichi=0
go_ichi=0
sen_go_ichi=0
mismatch=0
max_ichiman=int(2*(10**7)/(10**4))
for i in range(max_ichiman+1):
    if i*10**4==Y:
        ichiman=i
        break
    if i*10**4>Y:
        ichiman=i-1
        break
Y=Y-ichiman*10**4
for j in range(2):
    if j*5*10**3>=Y:
        gosen=j
        break
Y=Y-gosen*5*10**3
for k in range(5):
    if k*10**3==Y:
        sen=k
min_N=ichiman+gosen+sen
for i2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if i2*9>N-min_N:
        se_ichi=i2-1
        break
N=N-se_ichi*9
for j2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if j2*5>N-min_N:
        sen_go_ichi=j2-1
        break
N=N-sen_go_ichi*5
for k2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if k2==N-min_N:
        go_ichi=k2
        break
N=N-go_ichi
if N-min_N<0:
    mismatch=1
#print(ichiman, gosen, sen,N)
ichiman=ichiman-se_ichi-sen_go_ichi-go_ichi
gosen=gosen+2*go_ichi+sen_go_ichi
sen=sen+5*sen_go_ichi+10*se_ichi

if sen|gosen|ichiman<0:
    mismatch=1
if mismatch==1:
    sen=-1
    ichiman=-1
    gosen=-1
3print(se_ichi,go_ichi,sen_go_ichi,mismatch)
print(ichiman, gosen, sen)

### FIXED CODE ###

N,Y=map(int,input().split())
ichiman=0
gosen=0
sen=0
se_ichi=0
go_ichi=0
sen_go_ichi=0
mismatch=0
max_ichiman=int(2*(10**7)/(10**4))
for i in range(max_ichiman+1):
    if i*10**4==Y:
        ichiman=i
        break
    if i*10**4>Y:
        ichiman=i-1
        break
Y=Y-ichiman*10**4
for j in range(2+1):
    if j*5*10**3>Y:
        gosen=j-1
        break
Y=Y-gosen*5*10**3
for k in range(5):
    if k*10**3==Y:
        sen=k
min_N=ichiman+gosen+sen
if N-min_N<0:
    mismatch=1
#print(ichiman, gosen, sen,N)
for i2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if i2*9>N-min_N:
        se_ichi=i2-1
        break
N=N-se_ichi*9
for j2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if j2*5>N-min_N:
        sen_go_ichi=j2-1
        break
N=N-sen_go_ichi*5
for k2 in range(N-min_N+1):
    if N-min_N<0:
        mismatch=1
    if k2==N-min_N:
        go_ichi=k2
        break
N=N-go_ichi
if N-min_N<0:
    mismatch=1
#print(ichiman, gosen, sen,N)
ichiman=ichiman-se_ichi-sen_go_ichi-go_ichi
gosen=gosen+2*go_ichi+sen_go_ichi
sen=sen+5*sen_go_ichi+10*se_ichi

if sen|gosen|ichiman<0:
    mismatch=1
if mismatch==1:
    sen=-1
    ichiman=-1
    gosen=-1
#print(se_ichi,go_ichi,sen_go_ichi,mismatch)
print(ichiman, gosen, sen)
a=int(input())
ans=0
for i in a:
  ans+=1
print(ans)

### FIXED CODE ###

s=input()
ans=0
for i in s:
    ans+=int(i)
print(ans)
N = int(input())
p = [int(x) for x in input().split()]
cnt = 0
flag = True
for ind,i in enumerate(p):
    if(ind+1==i and flag):
        cnt+=1
        if(p[ind+1]==ind+2):
            flag = False
    else:
        flag = True
print(cnt)

### FIXED CODE ###

N = int(input())
p = [int(x) for x in input().split()]
cnt = 0
flag = True
for ind,i in enumerate(p):
    if(ind+1==i and flag):
        cnt+=1
        if(ind!=N-1):
            if(p[ind+1]==ind+2):
                flag = False
    else:
        flag = True
print(cnt)
# -*- coding: utf-8 -*-
from collections import Counter


N = int(input())
p = {}

for _ in range(N):
    s = input()
    if s not in p.keys():
        p[s] = 1
    else:
        p[s] += 1

M = int(input())

for _ in range(M):
    t = input()
    if t not in p.keys():
        p[t] = -1
    else:
        p[t] -= 1

print(max(max(p.values()), 0))


### FIXED CODE ###

# -*- coding: utf-8 -*-

A, B, C = map(int, input().split(" "))

if A + B >= C:
    print("Yes")
else:
    print("No")
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = {}
while cur != 0:
    root.add(cur)
    cur = before_ls[cur]
root.add(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    for j in range(M):
        is_updated = False
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
if is_updated:
    print("inf")
else:
    print(d[-1])
a,b,c = map(int, raw_input().split())

s = 3*c

print a,b,s-a-b
print s-(c+s-(s-a-b+s-a-c)),c,s-(s-a-b+s-a-c)
print a+b-c,s-b-c,s-a-c

### FIXED CODE ###

a = int(raw_input())
b = int(raw_input())
c = int(raw_input())

s = 3*c

print a,b,s-a-b
print s-(c+s-(s-a-b+s-a-c)),c,s-(s-a-b+s-a-c)
print a+b-c,s-b-c,s-a-c
N = int(input())
 
for i in range(9,1,-1):
	if N%i==0:
      if N//i==1:
        print("Yes")
        break
      for j in range(9,1,-1):
      	if N%(i*j)==0:
          print("Yes")
          break
      	print("No")
        break

### FIXED CODE ###

N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if i * j == N:
            break
    if i * j == N:
        print("Yes")
        break
    elif i == 9 and i * j != N:
        print("No")
N=input()
X=[list(map(int,input().split())) for i in range(N)]
X=sorted(X,key=lambda x:x[1])
s=0
t=0
for i in range(N):
  s+=X[i][0]
  if s>X[i][1]:
    print("No")
    break
  else:
    t+=1
if t==N:
  print("Yes")
    

### FIXED CODE ###

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X=sorted(X,key=lambda x:x[1])
s=0
t=0
for i in range(N):
  s+=X[i][0]
  if s>X[i][1]:
    print("No")
    break
  else:
    t+=1
if t==N:
  print("Yes")
a, b, c = map(int, input().split())
ans = 0
for i in range(n + 1):
  x = 0
  while i > 0:
    x += i % 10
    i //= 10
  if A <= x <= B:
    ans += 1
print(ans)


### FIXED CODE ###

n, a, b = map(int, input().split())
ans = 0
for i in range(n + 1):
  x, j = 0, i
  while j > 0:
    x += j % 10
    j //= 10
  if a <= x <= b:
    ans += i
print(ans)
n = int(input())
l = []
l2 = []

for i in range(n):
    a, b = list(map(int, input().split()))
    l.append([a,b])

for i in range(n-1):
    for j in range(i+1, n):
        dif1 = l[i][0] - l[j][0]
        dif2 = l[i][1] - l[j][1]
        l2.append(str(dif1) + ' ' + str(dif2))
##print(l2)

try:
    cnt = max(l2, key=l2.count)
except:
    cnt = 0
x, y = list(map(int, cnt.split()))

ans = 0

for i in range(len(l)):
    if [l[i][0] + x, l[i][1] + y] in l:
        ans += 1

print(n - ans)


### FIXED CODE ###

n = int(input())
l = []
l2 = []

for i in range(n):
    a, b = list(map(int, input().split()))
    l.append([a,b])
l.sort()

for i in range(len(l)-1):
    for j in range(i+1, len(l)):
        dif1 = l[i][0] - l[j][0]
        dif2 = l[i][1] - l[j][1]
        l2.append(str(dif1) + ' ' + str(dif2))
##print(l2)

try:
    cnt = max(l2, key=l2.count)
except:
    cnt = "1000000 1000000"
x, y = list(map(int, cnt.split()))

ans = 0

for i in range(len(l)):
    if [l[i][0] + x, l[i][1] + y] in l:
        ans += 1

print(n - ans)
import math

class DataSet():
    def __init__(self,a,b):
        self.a = a
        self.b = b

    def add_size(self):
        ans = self.a+self.b
        return int(math.log10(ans)+1)

def main():
    data_set = []
    ds_max = 200

    for i in range(0, ds_max):
        n = input().split()

        a = int(n[0])
        b = int(n[1])

        data_set.append(DataSet(a,b))

    for i in range(0, ds_max):
        ans = data_set[i].add_size()
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math

def main():
    data = []
    while 1:
        try:
            n = input().split()
            a = int(n[0])
            b = int(n[1])
            ans = int(math.log10(a+b)+1)
            data.append(ans)
        except EOFError:
            break

    for i in data:
        print(i)

if __name__ == "__main__":
    main()
"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    cnt_C = 0
    for n in range(1, len(s)):
        check_char = s[n]
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (len(s) - 1):
                ans = False
            
            cnt_C += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

cnt_C = 0
ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    length = len(s)

    n = 1
    for check_char in s[1:]:
        #print(check_char)
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")
n = int(input())
s = input()

from collections import Counter
rgb = dict(Counter(s))
p = rgb['R'] * rgb['G'] * rgb['B']
for i in range(1, len(s)//2):
    for j in range(len(s) - 2*i):
        if {s[j], s[j + i], s[j + 2*i]} == {'R', 'G', 'B'}:
            p -= 1
print(p)

### FIXED CODE ###

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

from collections import Counter
rgb = dict(Counter(s))
if len(rgb) < 3:
    print('0')
else:
    p = rgb['R'] * rgb['G'] * rgb['B']
    for i in range(1, (len(s)-1)//2 + 1):
        for j in range(len(s) - 2*i):
            if {s[j], s[j + i], s[j + 2*i]} == {'R', 'G', 'B'}:
                p -= 1
    print(p)
import collections
n=int(input())
s=[input() for _ in range(n)]
c=collections.counter(s)
common=c.most_common()
value,cnt=zip(*common)
common.sort(key=lambda x:x[0])
m=max(cnt)
for cc in most_common:
  if cc[1]==max:
    print(cc[0])

### FIXED CODE ###

import collections
n=int(input())
s=[input() for _ in range(n)]
c=collections.Counter(s)
common=c.most_common()
value,cnt=zip(*common)
common.sort(key=lambda x:x[0])
m=max(cnt)
for cc in common:
  if cc[1]==m:
    print(cc[0])
while(True):
    try:
        weight = float(input())

        if(weight <= 48.00):
            print("light fly")
        elif(weight <= 51.00):
            print("fly")
        elif(weight <= 54.00):
            print("bantam")
        elif(weight <= 57.00):
            print("feather")
        elif(weight <= 60.00):
            print("light")
        elif(weight <= 64.00):
            print("light welter")
        elif(weight <= 69.00):
            print("welter")
        elif(weight <= 75.00):
            print("light middle")
        elif(weight <= 81.00):
            print("middle")
        elif(weight <= 91.00):
            print("light heavy")
        else:
            print("heavy")
    except ValueError:
        break;



### FIXED CODE ###

# AOJ 0048
# Class
# 5/1/2019

min = 40.00
max = 150.00

measure = [min, 48.00, 51.00, 54.00, 57.00, 60.00, 64.00, 69.00, 75.00, 81.00, 91.00, max]
className = ['light fly',
         'fly',
         'bantam',
         'feather',
         'light',
         'light welter',
         'welter',
         'light middle',
         'middle',
         'light heavy',
         'heavy']

while True:
    try:
        weight = float(input())
    except:
        break;
    for i in range(11):
        if(measure[i] < weight and weight <= measure[i + 1]):
            print(className[i])
N=int(input())
if N>81:
  print("No")
else:
  i=1
  while N%i!=0 and i<10
    i+1
  if i==10:
    print("No")
  else:
    print("Yes")
    

### FIXED CODE ###

N=int(input())
for j in range(1,10):
    for i in range(1,10):
        if N==i*j:
            print("Yes")
            exit()
print("No")
n,a, b = map(int, input().split())
l = []
for i in range(10 ^100):
    l.extend([1]*a)
    l.extend([0]*b)

print(sum(l[:n]))

### FIXED CODE ###

n,a, b = map(int, input().split())
ans = n //(a+b) *a
tmp = n%(a+b)
ans += min(tmp,a)
print(ans)
import random
import sys

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}
ans = list(g_mem.values())
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        if edge.get(now):
            count = g_mem[now]
            queue = set(edge[now])
            while len(queue) > 0:
                next_now = queue.pop()
                if g_reached[next_now] == 0:
                    g_reached[next_now] = 1
                    count += g_mem[next_now]
                    queue |= edge[next_now]
                queue -= {now}
                now = next_now
            ans.append(count)


# print(ans)
print(max(ans))


### FIXED CODE ###

import random
import sys

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}
ans = list(g_mem.values())
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        if edge.get(now):
            count = g_mem[now]
            queue = set(edge[now])
            while len(queue) > 0:
                next_now = queue.pop()
                if g_reached[next_now] == 0:
                    g_reached[next_now] = 1
                    count += g_mem[next_now]
                    queue |= edge[next_now]
                queue -= {now}
                now = next_now
            ans.append(count)


# print(ans)
if len(ans) > 0:
    print(max(ans))
else:
    print(1)
from math import factorial


def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


def p_d():
    N, K = map(int, input().split())
    n = N - K + 1
    mod = 10 ** 9 + 7

    for i in range(1, K + 1):
        # print(n, i, n - i)
        c = cmb(n, min(i, abs(n - i)))
        # c = cmb(n, i)
        k = cmb(K - 1, i - 1)
        print(c * k % mod)


if __name__ == '__main__':
    p_d()


### FIXED CODE ###

from math import factorial


def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(abs(n - r))


def p_d():
    N, K = map(int, input().split())
    n = N - K + 1
    mod = 10 ** 9 + 7

    for i in range(1, K + 1):
        c = cmb(n, i)
        k = cmb(K - 1, i - 1)
        print(c * k % mod)


if __name__ == '__main__':
    p_d()
while True:
    n, m, a = map(int, input().split())

    if n + m + a == 0:
        break

    lines = list(reversed(sorted([tuple(map(int, input().split())) for _ in range(m)])))

    replace = list(range(1, n+1))

    for l in lines:
        h, p, q = l

        p -= 1
        q -= 1

        replace[p], replace[q] = replace[q], replace[p]

    a -= 1

    for _ in range(n):
        a = replace[a]

    print(a)

### FIXED CODE ###



while True:
    # num_columns: ????£?????????°
    # num_lines: ?¨??£?????????°(???????????????2????´???????????????°)
    # entry: ????????????????????????????§?????????´????????????
    num_columns, num_lines, entry = map(int, input().split())

    if num_columns == 0 and num_lines == 0 and entry == 0:
        break

    lines = []
    for _ in range(num_lines):
        height, p, q = map(int, input().split())
        lines.append((height, p-1, q-1)) # ????????????0?????????????§????????????§???????????????

    # lines??????????????????????????§???????????????????????????????´?????¨??£???????????????\???????????§
    # ??????????????????????????°??????????????????????????????
    lines.sort()
    lines.reverse()
    # ??????2??????????????§???lines????????????????´??????§?????????????????¶

    result = list(range(1, num_columns+1)) # ??????????§????????????´????????¨????????????

    for line in lines:
        height, p, q = line
        
        # ?????????`replace`???p????????¨q?????????????????????
        result[p], result[q] = result[q], result[p]

    for index, element in enumerate(result):
        if element == entry:
            print(index + 1) # ????????????0?????????????§????????????§???????????????
            break
    # print(result.index(entry) + 1) ??§?????????
a = str(input())

if str.isupper() == True:
  print("A")
else:
  print("a")



### FIXED CODE ###

a = input()

if a.isupper():
  print("A")
else:
  print("a")
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
while M>0:
    if A[0]//2<A[1]:
        A_0=A[0]
        i=0
        while A[i]>=A_0 and i<M and i<N:
            A[i]=A[i]//2
            i+=1
        A.sort(reverse=True)
        M-=i
    else:
        A[0]=A[0]//2
        M-=1
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: x*(-1),list(map(int,input().split()))))
A.sort()
B=[]
for i in range(N):
    heapq.heappush(B,A[i])
for i in range(M):
    heapq.heappush(B,(((heapq.heappop(B))*(-1))//2)*(-1))
print((sum(B))*(-1))
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


ans = 1
color = [0, 0, 0]
for i in range(n):
    ans = ans * color.count(A[i]) % mod
    color[color.index(A[i])] += 1



print(ans)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()


ans = 1
color = [0, 0, 0]
for i in range(n):
    ans = ans * color.count(A[i]) % mod
    for j in range(3):
        if color[j] == A[i]:
            color[j] += 1
            break



print(ans)