Problem:


Score: 500 points

Problem Statement

N people are standing in a queue, numbered 1, 2, 3, ..., N from front to back. Each person wears a hat, which is red, blue, or green.

The person numbered i says:

"In front of me, exactly A_i people are wearing hats with the same color as mine."

Assuming that all these statements are correct, find the number of possible combinations of colors of the N people's hats.

Since the count can be enormous, compute it modulo 1000000007.

Constraints

1 \leq N \leq 100000

0 \leq A_i \leq N-1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_N

Output

Print the number of possible combinations of colors of the N people's hats, modulo 1000000007.

Sample Input 1

6
0 1 2 3 4 5

Sample Output 1

3

We have three possible combinations, as follows:

Red, Red, Red, Red, Red, Red

Blue, Blue, Blue, Blue, Blue, Blue

Green, Green, Green, Green, Green, Green

Sample Input 2

3
0 0 0

Sample Output 2

6

Sample Input 3

54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

Sample Output 3

115295190



Sample input:
6
0 1 2 3 4 5


Sample output:
3

Submission status: Accepted

Solution code:
def examE(mod):
    N = I()
    A = LI()
    a =[0,0,0]
    cur = 1
    for i in A:
        if a[0]==i:
            if a[0]==a[1]:
                if a[1]==a[2]:
                    cur *= 3
                else:
                    cur *=2
            a[0]+=1
        elif a[1]==i:
            if a[1] == a[2]:
                cur *= 2
            a[1] +=1
        elif a[2]==i:
            a[2]+=1
        else:
            cur *=0
        a.sort(reverse=True)
        cur %=mod
    print(cur)
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
ans = 1
d = [0,0,0]
for x in a:
  tmp = 0
  for k in range(3):
    if x == d[k]:
      if tmp == 0:
        d[k] += 1
      tmp += 1
  ans *= tmp
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n=inp()
    a=inpl()
    ans=1
    num=[0,0,0]
    for i in range(n):
        cnt=0
        index=0
        for j in range(3):
            if num[j]==a[i]:
                cnt+=1
                index=j
        num[index]+=1
        if cnt==1:
            ans=ans%mod
            continue
        elif cnt==2:
            ans=(ans*2)%mod
        elif cnt==3:
            ans=(ans*3)%mod
        else:
            print(0)
            return
    print(ans%mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 1000000007
ans = 1
tmp = [0] * n
for i in range(n):
    if a[i] == 0:
        ans *= 3 - tmp[0]
        tmp[0] += 1
    else:
        ans *= tmp[a[i]-1] - tmp[a[i]]
        ans %= mod
        tmp[a[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 1000000007

n = int(input())
a = np.array(list(map(int, input().split())))
tails = np.full((3,), -1)
ind = np.arange(3)
res = 1
for aa in a:
    filt = tails == (aa-1)
    s = filt.sum()
    if s == 0:
        print(0)
        exit(0)
    res *= s
    res %= MOD
    i = ind[filt][0]
    tails[i] = aa
print(res)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
ans=1
B=[0,0,0]
for i in range(n):
  ct=0
  chk=False
  for j in range(3):
    if B[j]==A[i]:
      ct+=1
      if not chk:
        B[j]+=1
        chk=True
  ans=(ans*ct)%mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

mod = 1000000007

A = np.zeros(N)

ans = 1

for i in range(N):
    hoge = D[i]
    if hoge == 0:
        ans *= int(3-A[hoge])
        A[hoge] += 1
    else:
        ans *= int(A[hoge-1]-A[hoge])
        A[hoge] += 1
    
    if ans > mod:
        ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


N = int(readline())
A = list(map(int, readline().split()))
P = 10**9 + 7


a = 1
state = [0, 0, 0]

for i in range(N):
    c = state.count(A[i]) 
    a *= c
    a %= P
    if c == 0:
        print(0)
        exit(0)
    state[state.index(A[i])] = A[i] + 1

print(a)

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()

R = 0
G = 0
B = 0

Z = 1

for aa in A:
    a = int(aa)
    x = 0
    if a == R and a == G and a == B:
        x = x + 3
        R = R + 1
    elif a == R and a == G:
        x = x + 2
        R = R + 1
    elif a == R and a == B:
        x = x + 2
        R = R + 1
    elif a == G and a == B:
        x = x + 2
        G = G + 1
    elif a == R:
        x = x + 1
        R = R + 1
    elif a == B:
        x = x + 1
        B = B + 1
    elif a == G:
        x = x + 1
        G = G + 1
    Z = Z * x % 1000000007

print(Z)

Submission status: Accepted

Solution code:
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    try:
        i=C.index(a)
        r=r*sum([1 if c==a else 0 for c in C])%m
        C[i]+=1
    except:
        print(0)
        exit()
print(r)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
c=1
for i in range(n):
    c*=b.count(a[i])
    c%=1000000007
    if b[0]==a[i]:
        b[0]+=1
    elif b[1]==a[i]:
        b[1]+=1
    else:
         b[2]+=1
print(c)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=[0]*3
ans=1
mod=10**9+7
for i in range(n):
	q=0
	if a[i]==cnt[0]:
		q+=1
	if a[i]==cnt[1]:
		q+=1
	if a[i]==cnt[2]:
		q+=1
	if a[i]==cnt[0]:
		cnt[0]+=1
	elif a[i]==cnt[1]:
		cnt[1]+=1
	else:
		cnt[2]+=1
	ans*=q
	ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

cnt = [-1, -1, -1]
ans = 1
for a in A:
    num = 0
    i = -1
    for j in range(3):
        if a == cnt[j] + 1:
            num += 1
            i = j
    if num == 0:
        ans = 0
        break
    ans *= num
    ans %= MOD
    cnt[i] = a

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * N
dp[0] = 3
r = 1
g = 0
b = 0
if a[0] != 0:
  dp[0] = 0
for i in range(N - 1):
  f = 0
  if a[i + 1] == r:
    dp[i + 1] += dp[i]
    f = 0
  if a[i + 1] == g:
    dp[i + 1] += dp[i]
    f = 1
  if a[i + 1] == b:
    dp[i + 1] += dp[i]
    f = 2
  if f == 0: r += 1
  if f == 1: g += 1
  if f == 2: b += 1
  dp[i + 1] %= mod
print((dp[-1]) % mod)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * 3
    ans = 1
    for a in A:
        ans = (ans * cnt.count(a)) % MOD
        try:
            c = cnt.index(a)
        except ValueError:
            print(0)
            return
        cnt[c] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
r = 1
n, m, l = 0, 0, 0
for A in As:
  if n == m == l == A:
    r = r*3%1000000007
    l += 1
  elif n < m == l == A:
    r = r*2%1000000007
    l += 1
  elif m < l == A:
    r = r*1%1000000007
    l += 1
  elif n == m == A < l:
    r = r*2%1000000007
    m += 1
  elif n < m == A < l:
    r = r*1%1000000007
    m += 1
  elif n == A < m:
    r = r*1%1000000007
    n += 1
  else:
    r = 0
print(r)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
P = 1000000007
dp = [0] *(N + 1)
dp[0] = 1
color = [0, 0, 0]
for i in range(N):
    count = 0
    check= True
    for j in range(3):
        if color[j] == A[i]:
            count += 1
            if check:
                color[j] += 1
                check = False
    dp[i + 1] += (dp[i] * count)%P
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))

rgb = [0 for i in range(3)]

count = 1
m = 1000000007

for i in range(n):
    a = arr[i]
    temp = 0
    hoge = -1
    for j in range(3):
        if rgb[j] == a:
            hoge = j
            temp += 1
    rgb[hoge] += 1
    if temp == 0:
        count = 0
        break
    else:
        count *= temp
        count = count%m

# print(rgb)
print(count)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

cnt = 1
last = [-1,-1,-1]

for a in A:
    cnt *= last.count(a-1)
    cnt %= MOD
    if cnt == 0:
        break
    last[last.index(a-1)] += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]

    mod = 1000000007
    rgb = [0, 0, 0]
    count = 1
    for i in range(N):
        a = A[i]
        if rgb[0] == a:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 3
                    count %= mod
                else:
                    count *= 2
                    count %= mod
            rgb[0] += 1
        else:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 2
                    count %= mod
                rgb[1] += 1
            else:
                if rgb[2] == a:
                    rgb[2] += 1
                else:
                    count = 0
                    break
    
    print(count)
                    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
LARGE = 1000000007


def solve(n, a_list):

    x = -1
    y = -1
    z = -1
    res = 1

    for i in range(n):
        c = 0
        a = a_list[i]
        if x == a - 1:
            c += 1
        if y == a - 1:
            c += 1
        if z == a - 1:
            c += 1
        if x == a - 1:
            x += 1
        elif y == a - 1:
            y += 1
        else:
            z += 1
        res *= c
        res %= LARGE
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(6, [0, 1, 2, 3, 4, 5]) == 3
    assert solve(3, [0, 0, 0]) == 6


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A =list(map(int,input().split()))
a=1
b=[0,0,0]
for i in A:
    t=b.count(i)
    if i==b[0]:
        b[0]+=1
    elif i==b[1]:
        b[1]+=1
    elif i==b[2]:
        b[2]+=1
    a=a*t%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
#E
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

R = 0
G = 0
B = 0
ans = -1
count = 1
for i,a in enumerate(A):
    if i == 0:
        if a != 0:
            ans = 0
            break
        else:
            R = 1
            count*=3
    else:
        if R == a and G == a and B == a:
            count*=3
            R+=1
        elif R == a and G == a:
            count*=2
            R+=1
        elif R == a and B == a:
            count*=2
            R+=1
        elif G == a and B == a:
            count*=2
            G+=1
        elif R == a:
            R+=1
        elif G == a:
            G+=1
        elif B == a:
            B+=1
        else:
            ans = 0
            break
        
            
if ans == 0:
    print(ans)
else:
    ans = count
    print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

ans=1
b = [-1,-1,-1]
for i in a:
    flag = True
    count=0
    for j in range(3):
        if b[j] == i - 1:
            if flag:
                b[j] += 1
                flag=False
            count +=1
    ans = ans * count % 1000000007
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(input())
a = list(map(int, input().split()))
zero = a.count(0)

if zero == 1:
	ans = 3
elif 2 <= zero <= 3:
	ans = 6
else:
	ans = 0

cnt = [0 for _ in range(n)]
for x in a:
	cnt[x] += 1
	if cnt[x] > 3:
		ans = 0
	if x > 0:
		ans *= cnt[x-1]
		ans %= MOD
		cnt[x-1] -= 1

print(ans)

Submission status: Accepted

Solution code:

n = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    d = collections.defaultdict(int)
    t = 1
    for i in range(n):
        if a[i] == 0:
            t *= 3 - d[0]
            d[a[i]] += 1
        else:
            t *= d[a[i]-1] - d[a[i]]
            d[a[i]] += 1
        t %= mod
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
counts = [0,0,0]
out = 1
for i in range(N):
  cur = 0
  for j in range(3):
    if counts[j] == A[i]:
      cur += 1
  out *= cur
  out %= 1000000007
  for j in range(3):
    if counts[j] == A[i]:
      counts[j] += 1
      break
print(out)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
data=[0,0,0]
for u in a:
    cnt=0
    k=-1
    for i in range(3):
        if u==data[i]:
            k=i
            cnt+=1
    ans=ans*cnt%mod
    if k!=-1:
        data[k]+=1
print(ans)

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

con = 10 ** 9 + 7
#処理内容
def main():
	N = int(input())
	A = getlist()
	RGB = [0, 0, 0]
	ans = 1
	for i in range(N):
		cnt = 0
		jud = "No"
		for j in range(3):
			if A[i] == RGB[j]:
				cnt += 1
				if jud == "No":
					RGB[j] += 1
					jud = "Yes"
		ans = (ans * cnt) % con

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

d = [0 for i in range(n+1)]
ans = 1
for i in range(n):
    if a[i] == 0:
        ans *= 3-d[0]
        d[0] += 1
    else:
        d[a[i]] += 1
        ans *= d[a[i]-1] - d[a[i]] + 1
        ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 3
ans = 1
for a in aaa:
    ans = ans * dp[a] % MOD
    dp[a] -= 1
    dp[a + 1] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
MOD = 1000000007

def calc(A):
    CA = Counter(A)
    if max(CA.values()) > 3:
        return 0
    
    pop = [0]*(N+3)
    pop[-1] = 3
    
    res = 1
    for a in A:
        if pop[a-1] <= 0:
            return 0
        res = (res*pop[a-1]) %MOD
        pop[a-1] -= 1
        pop[a] += 1
        
    
    
        
    return res
        

print(calc(A))

Submission status: Accepted

Solution code:
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  if ls[i] in RGB:
    x=RGB.count(ls[i])
    ans=(ans*x)%MOD
    y=RGB.index(ls[i])
    RGB[y]+=1
  else:
    ans=0
    break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    N = read_int()
    A = read_ints()
    print(solve(N, A))


MOD = 1000000007


def solve(N, A):
    c = 1
    nums = [0, 0, 0]

    for a in A:
        z = nums.count(a)
        if z == 0:
            return 0
        c *= z
        c %= MOD
        nums[nums.index(a)] = a + 1

    return c


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def main():
    n, *a = map(int, sys.stdin.read().split())

    res = 1
    rgb = [0, 0, 0]
    for i in range(n):
        cur = a[i]
        c = rgb.count(cur)
        res = res * c % MOD
        if cur == rgb[0]:
            rgb[0] += 1
        elif cur == rgb[1]:
            rgb[1] += 1
        elif cur == rgb[2]:
            rgb[2] += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
color=[0,0,0]
ans=1
for i in a:
  ans*=color.count(i)
  ans%=mod
  for j in range(3):
    if color[j]==i:color[j]+=1;break
print(ans%mod)

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


# Code

n = intput()

a = list(intsput())

rgb = [0, 0, 0]

ans = 1
for i in range(n):
    x = a[i]
    cnt = 0
    placed = False
    for j in range(3):
        if rgb[j] == x:
            if not placed:
                rgb[j] += 1
                placed = True
            cnt += 1
        
    ans *= cnt
    ans %= 10 ** 9 + 7

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mod = 10 ** 9 + 7

d = defaultdict(int)
d[-1] = 3

ret = 1
for a in A :
    ret = ret * d[a-1] % mod
    d[a-1] -= 1
    d[a] += 1
    
print(ret)

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
cnt = [0, 0, 0]
ans = 1
for a in A:
    c = 0
    for j in range(3):
        if cnt[j] == a:
            c+=1
            if c == 1:
                cnt[j]+=1
    ans*=c
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

m = 1000000007
b = [-1,-1,-1]
ans = 1

for i in range(n):
    ans *= b.count(a[i]-1)
    ans%=m
    if ans ==0:
        print(0)
        exit()
    for j in range(3):
        if b[j]==a[i]-1:
            b[j]+=1
            break

print(ans%m)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())

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

lis = [0,0,0]
ans = 1

for i in range(N):

    na = A[i]
    ind = 0
    nn = 0

    for j in range(3):
        if lis[j] == na:
            nn += 1
            ind = j

    lis[ind] += 1

    if nn == 0:
        ans *= 0

    elif nn == 2:
        ans *= 2
    elif nn == 3:
        ans *= 3

    ans %= mod
    #print (lis)

print (ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
f = [0] * 3
ans = 1
m = 1000000007
for x in a:
  c = 0
  for y in f:
    if x == y:
      c += 1
  ans = ans * c % m
  for i in range(3):
    if f[i] == x:
      f[i] += 1
      break
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

remain = 3
s = [0,0,0]
ans = 1
for i in a:
    k = s.count(i)
    ans *= s.count(i)
    ans %= mod
    if k == 0:
        break
    s[s.index(i)] += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    cnt=1
    now=[0,0,0]
    mod=10**9+7
    for i in a:
        cnt=(cnt*now.count(i))%mod
        for j in range(3):
            if now[j]==i:
                now[j]+=1
                break
    print(cnt)
main()

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
p = [-1,-1,-1]
ans = 1
for i in range(N):
    a = A[i]
    ans *= p.count(a-1)
    ans %= mod
    for j in range(3):
        if p[j]==a-1:
            p[j] = a
            break
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

al = []

co = 1

for i in range(n):
    if a[i] == 0:
        co *= max(0,(3-len(al)))
        al.append(0)
    else:
        on = 0
        flag = True
        for j in range(len(al)):
            if al[j] == a[i]-1:
                on += 1
                if flag == True:
                    al[j] += 1
                    flag = False
        co *= on
        co %= mod
print(co)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = [0 for i in range(N)]
count[-1] = 3

MOD = 1000000007
ways = 1
for n in A:
    ways *= count[n-1]
    count[n-1] -= 1
    count[n] += 1
    ways %= MOD
print(ways)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
color = [0,0,0]
ans = 1
for i in a:
  mini = 0
  al = 0
  for key,j in enumerate(color):
    if i == j:
      if al == 0:
        al = 1
        color[key] += 1
      mini += 1
  ans = (ans * mini) % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 1
count = np.zeros(N + 1, dtype="int")
count[0] = 3

for i in A:
    ans *= max(0, count[i] - count[i + 1])
    ans %= 1000000007
    count[i + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007

D = [0] * 3

ans = 1
for i in A:
  c = 0
  for j in range(3):
    if i == D[j]:
      if c == 0:
        D[j] += 1
      c += 1
  ans = ans * c % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

res = 1
tank = [0,0,0]

for e in a:
    cnt = 0
    idx = -1
    if tank[0] == e:
        cnt += 1
        idx = 0
    if tank[1] == e:
        cnt += 1
        idx = 1       
    if tank[2] == e:
        cnt += 1
        idx = 2
    
    if cnt == 0:
        print(0)
        exit()
    
    res = res*cnt%mod
    tank[idx] += 1

print(res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    d = [0,0,0]
    ans = 1
    for i in a:
        ans *= d.count(i)
        ans %= mod
        if ans == 0:
            break
        for j in range(3):
            if d[j] == i:
                d[j] += 1
                break
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

mod=1000000007

DP=[0,0,0]
ANS=1

for a in A:
    ANS=ANS*DP.count(a)%mod
    if ANS==0:
        print(0)
        sys.exit()
    x=DP.index(a)
    DP[x]+=1

print(ANS)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

A = [x + 1 for x in A]

counter = [0] * (N+100)
counter[0] = 3
answer = 1
for x in A:
    answer *= counter[x-1]
    counter[x-1] -= 1
    counter[x] += 1
    answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
ans=1
rgb=[0]*3
for i in range(n):
    f=0
    for j in range(3):
        if l[i]==rgb[j]:
            if f==0:
                rgb[j]+=1
            f+=1
    ans*=f
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    n=int(input())
    A=list(map(int,input().split()))
    RGB=[0]*3
    ans=1
    for a in A:
        tmp=0
        for k in RGB:
            if a==k:
                tmp+=1
        ans*=tmp
        ans%=mod
        for i,k in enumerate(RGB):
            if a==k:
                RGB[i]+=1
                break
        else:
            return 0
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
# import math
def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def main():
    n = getN()
    nums = getlist()
    ans = 1
    bc, bv, bb = -1, -1, -1
    for num in nums:
        tmp = 0
        added = 0
        if num == bc + 1:
            tmp += 1
            if not added:
                bc += 1
                added = 1

        if num == bv + 1:
            tmp += 1
            if not added:
                bv += 1
                added = 1

        if num == bb + 1:
            tmp += 1
            if not added:
                bb += 1
                added = 1

        ans *= tmp
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
P = 10**9+7
ans = 1
X = [0, 0, 0]
for a in A:
    c = X.count(a)
    ans = ans * c % P
    if X[0] == a:
        X[0] += 1
    elif X[1] == a:
        X[1] += 1
    else:
        X[2] += 1
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
AA = inpl()

cnts = [0]*(N+1)
cnts[-1] = 3

ans = 1
for a in AA:
    ans *= (cnts[a-1] - cnts[a])
    ans %= mod
    cnts[a] += 1


print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline 

n = int(input())
#s = input()
a = [int(i) for i in readline().split()]
#m = [[int(i) for i in readline().split()] for _ in range(n)]

MOD = 1000000007

ans = 1
res = [0,0,0]

for ai in a:
    c = res.count(ai)
    ans *= c
    ans %= MOD
    for i in range(3):
        if res[i] == ai:
            res[i] += 1
            break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = 1
r,g,b = 0,0,0

for x in a:
    ans *= [r,g,b].count(x)
    ans %= 1000000007
    if r == x:r+=1
    elif g == x:g +=1
    elif b == x:b +=1
    else:
        print(0)
        exit()

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N + 1)]

for a in A:
    ans = ans * cnt[a] % MOD
    if ans == 0:
        break
    cnt[a] -= 1
    cnt[a+1] += 1

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))

ans=1

d={}

ch=0

mod=10**9+7

for i in range(n):
  if a[i]==0:
    if 0 not in d:
      d[0]=1
      ans*=3
    else:
      if d[0]==1:
        d[0]=2
        ans*=2
      elif:
        d[0]=3
      else:
        ch+=1
        break
      
  else:
    if a[i] not in d:
      d[a[i]]=1
      if a[i]-1 not in d:
        ch+=1
        break
      else:
        ans*=d[a[i]-1]
    else:
      if d[a[i]]==1:
        d[a[i]]=2
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=2:
            ans*=d[a[i]-1]-1
          else:
            ch+=1
            break
      elif:
        d[a[i]]=3
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=3:
            ans*=1
          else:
            ch+=1
            break
      else:
        ch+=1
        break
        
  ans=(ans%mod)
  
if ch==0:
  print(ans)
else:
  print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))

ans=1

d={}

mod=10**9+7

for i in range(n):
  if a[i]==0:
    if 0 not in d:
      d[0]=1
      ans*=3
    else:
      if d[0]==1:
        d[0]=2
        ans*=2
      else:
        d[0]=3
      
  else:
    if a[i] not in d:
      d[a[i]]=1
      ans*=d[a[i]-1]
    else:
      if d[a[i]]==1:
        d[a[i]]=2
        ans*=d[a[i]-1]-1
      else:
        d[a[i]]=3
        ans*=1
        
  ans=(ans%mod)
  
print(ans)