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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  l=LI()

  if l[0]!=0:
    return 0

  a=[0]*3

  ans=1
  for x in l:
    ans*=a.count(x)
    c=a.count(x)
    if c>0:
      a[a.index(x)]+=1

    ans%=mod

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n = int(input())
vals = map(int, input().split(" "))
cur_vals = [-1, -1, -1]

M = 1000000007
out = 1
for val in vals:
    before_val = val-1
    before_val_num = sum([1 for cur_val in cur_vals if cur_val == before_val])
    if before_val_num == 0:
        out = 0
        break
    out = (out * before_val_num) % M
    tar_i = cur_vals.index(before_val)
    cur_vals[tar_i] = val

print(out)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	if cnt == 0:
		break
	n_colors[n_colors.index(x)] += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = input()
    aa = map(int, raw_input().split())
    dic = {(0, 0, 0): 1}
    for a in aa:
        next_dic = {}
        for (x, y, z), c in dic.iteritems():
            if a == x:
                key = (x + 1, y, z)
                next_dic[key] = next_dic.get(key, 0) + c
            if a == y:
                key = (x, y + 1, z)
                next_dic[key] = next_dic.get(key, 0) + c
            if a == z:
                key = (x, y, z + 1)
                next_dic[key] = next_dic.get(key, 0) + c
        dic = next_dic
    count = 0
    for c in dic.itervalues():
        count = (count + c) % 1000000007
    print count


main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

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

Submission status: Accepted

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

mod = 1000000007

RGB = [1,0,0]
n_cols = 1
ans = 1

dp=[0]*(N+1)

#A[0]による初期条件
dp[0]=2
dp[1]=1

if A[0]>0:
  print(0)
  exit()
  
for a in A[1:]:
  if a==0:
    n_cols += 1
    dp[0]-=1
    dp[1]+=1
    if n_cols ==4:
      print(0)
      exit()
      
  else:
    if dp[a]==0:
      print(0)
      exit()
    else:
      ans *= dp[a]
      ans %= mod
      dp[a]-=1
      dp[a+1]+=1
      
if n_cols==1:
  ans *= 3
else:
  ans *= 6
ans %=mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    hat=[0,0,0]
    colors=0
    ans=1

    for i in range(N):
        if A[i]==0:
            ans *= 3 - colors
            colors += 1
            continue
        factor=0
        flag=1
        for j in range(colors):
            if A[i] == hat[j]+1:
                factor += 1
                hat[j] += flag
                flag = 0
        ans = (ans * factor) % MOD

    print(ans)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    mod = 1000000007
    n = int(input())
    cnt = [0] * (n + 2)
    cnt[0] = 3
    res = 1
    for x in input().split():
        v = int(x)
        res *= cnt[v] - cnt[v + 1]
        res %= mod
        cnt[v + 1] += 1
    print(res)

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(lambda x: int(x)+1, input().split()))
MOD = 1000000007

up = [0] * (n+1)
up[0] = 3
p = 1
for i in a:
    if up[i - 1] < up[i]:
        print(0)
        exit()
    p = (p * (up[i - 1] - up[i]) % MOD)
    up[i] += 1

print(p % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

color = [-1,-1,-1]
ans = 1
for i in range(N):
    if A[i]-1 in color:
        num1 = 0
        num2 = 0
        for j in range(3):
            if color[j]==A[i]-1:
                num1 += 1
            if color[j]==A[i]:
                num2 += 1
        if num1==3 and num2==0:
            ans *= 3
            ans %= MOD
        elif num1==2 and num2==1:
            ans *= 2
            ans %= MOD
        elif num1==1 and num2==2:
            ans *= 1
            ans %= MOD
        elif num1==2 and num2==0:
            ans *= 2
            ans %= MOD
        elif num1==1 and num2==1:
            ans *= 1
            ans %= MOD
        elif num1==1 and num1==1:
            ans *= 1
            ans %= MOD
        for j in range(3):
            if color[j]==A[i]-1:
                color[j]+=1
                break
    else:
        print(0)
        break
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    N=int(input())
    MOD=1000000007
    
    a=list(map(int,input().split()))
    c=[0,0,0]
    ans=1
    for i in range(N):

        if a[i]!=c[0] and a[i]!=c[1] and a[i]!=c[2]:
            print(0)
            sys.exit()

        if c[1]==c[0] and c[2]==c[0]:
            ans=(ans*3)%MOD
            c[0]+=1

        elif c[0]==c[1]:
            if c[0]==a[i]:
                c[0]+=1
                ans=(ans*2)%MOD
            else:
                c[2]+=1

        elif c[0]>c[1] and c[1]==c[2]:
            if c[0]==a[i]:
                c[0]+=1
            else:
                ans=(ans*2)%MOD
                c[1]+=1
            
        else:
            if c[0]==a[i]: c[0]+=1
            if c[1]==a[i]: c[1]+=1
            if c[2]==a[i]: c[2]+=1
        
        c.sort(reverse=True)
    print(ans)


 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 1
colors = [0] * 3
mod = 10**9 + 7

for a in A:
    ans = (ans * colors.count(a)) % mod
    if ans != 0:
        i = colors.index(a)
        colors[i] += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    d = defaultdict(int)
    a = LI()
    ans = 1
    d[0] = 3
    for i in range(n):
        y = d[a[i]]
        ans *= y
        ans %= mod
        d[a[i]] -= 1
        d[a[i] + 1] += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans = 1
numofcolor = [0] * (N+1)
numofcolor[0] = 3
for i in range(N):
    ans *= numofcolor[A[i]]
    ans %= 1000000007
    numofcolor[A[i]] -= 1
    numofcolor[A[i]+1] += 1
print(ans)

Submission status: Accepted

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

ans = 3
hats = [1, 0, 0]

if n == 1:
    if A[0] == 0:
        print(3)
    else:
        print(0)
    exit()


if A[0] != 0:
    print(0)
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print(0)
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

c = [-1,-1,-1]

ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9+7
N = int(input())
A = inpl()
ans = 1
nc = [0] * 3
for i in range(N):
    k = 0
    a = A[i]
    while nc[k] > a:
        k += 1
        if k > 2:
            print(0)
            exit()
    if nc[k] < a:
        print(0)
        exit()
    if k <= 1 and nc[k+1] == a:
        s = 2
        if k == 0 and nc[k+2] == a:
            s = 3
        ans = ans * s % MOD
    nc[k] += 1
print(ans)

Submission status: Accepted

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

MOD=10**9+7
rgb=[-1]*3

count=1
buf=0
for i in range(n):
    c=0
    for j in range(3):
        if rgb[j]+1==a[i]:
            c+=1
            buf=j
    #print(rgb,c)
    count*=c
    count%=MOD
    rgb[buf]+=1
print(count)

Submission status: Accepted

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

ans = 1
res = 10 ** 9 + 7
B = 0
R = 0
G = 0
for a in A:
    cnt = 0
    if a == B:
        cnt += 1
    else:
        pass
    if a == R:
        cnt += 1
    else:
        pass
    if a == G:
        cnt += 1
        G += 1
    elif a == R:
        R += 1
    else:
        B += 1
    ans = ans * cnt % res
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
a=list(map(int,input().split()))
c=1
r=0
g=0
b=0
for x in a:
    tmp=0
    if x==b:
        tmp+=1
    if x==g:
        tmp+=1
    if x==r:
        tmp+=1
    if x==b:
        b+=1
    elif x==g:
        g+=1
    else :
        r+=1
    c*=tmp
    c%=mod
print(c)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    a_s = LI()
    d = [0, 0, 0]
    ans = 1
    for i in a_s:
        flag = True
        tmp = 0
        for index, j in enumerate(d):
            # print(i, j)
            if j == i:
                tmp += 1
                if flag:
                    d[index] += 1
                    flag = False
        ans = ans * tmp % MOD
        # print(d, tmp, i, ans)
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

DIV = 1000000007

ls = [0]*100000

ans = 1
for i in a:
    ls[i] += 1
    if i == 0:
        ans *= 4 - ls[i]
    else:
        ans *= ls[i-1]-ls[i]+1

    ans %= DIV

print(ans)

Submission status: Accepted

Solution code:
n,*d=map(int,open(0).read().split())
a,b,c=0,0,0
ans=1
for i in d:
    ans=ans*[a,b,c].count(i)%1000000007
    if i==a:
        a+=1
    elif i==b:
        b+=1
    elif i==c:
        c+=1
print(ans)

Submission status: Accepted

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

stack = [0,0,0]

ans = 1
for a in al:
    p = stack.count(a)
    ans *= p
    ans %= 1000000007
    for i in range(3):
        if stack[i] == a:
            stack[i] += 1
            break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD=10**9+7
n=int(input())
l=list(map(int,input().split()))
lc=[0]*(n+1)
ans=1
tmp=3
for i in l:
    if i==0:
        ans*=tmp
        ans%=MOD
        tmp-=1
    else:
        ans*=lc[i-1]
        ans%=MOD
        lc[i-1]-=1
    lc[i]+=1
print(ans)

Submission status: Accepted

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

cnt = [0] * (max(A) + 2)
cnt[-1] = 1
ans = 1
for a in A:
    if a == 0:
        cnt[0] += 1
        continue
    ans = (ans * (cnt[a - 1] - cnt[a])) % mod
    cnt[a] += 1

if max(cnt) == 1:
    print((ans*3) % mod)
elif max(cnt) == 3:
    print((ans * 6) % mod)
elif max(cnt) == 2:
    print((ans * 6) % mod)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
al=list(map(int,input().split()))
num=[0 for i in range(n+2)]
num[-1]=3
ans=1

for i in range(n):
    ans*=num[al[i]-1]
    ans=ans%1000000007
    num[al[i]-1]-=1
    num[al[i]]+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np


if __name__ == "__main__":
    n = int(input())
    a = np.array(list(map(int, input().split())))
    mod = 10**9+7

    memo = np.zeros(n+10, dtype=int)
    memo[0] = 3
    ans = 1
    for i in a:
        mae = memo[i]
        now = memo[i+1]
        ans *= mae-now
        ans %= mod

        memo[i+1] += 1

    print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
N = int(input())
A = [int(i) for i in input().split()]
M = [0]*10**5

ans = 1
for i, a in enumerate(A):
    if a == 0:
        ans *= 3-M[0]
        M[0] += 1
    else:
        ans *= M[a-1]-M[a]
        M[a] += 1
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
M = 1000000007
N = int(input())
A = list(map(int, input().split()))
count = [0 for i in range(N+1)]
count[N] = 3
ans = 1
for ai in A:
    ans = (ans * count[ai-1]) % M
    count[ai] += 1
    count[ai-1] -= 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#mitsui e
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

a=-1
b=-1
c=-1

ans=1

for i in range(0,n):
	tmp=0
#	print(s[i])
	if(s[i]-1==a):
		tmp+=1
	if(s[i]-1==b):
		tmp+=1
	if(s[i]-1==c):
		tmp+=1
	ans*=tmp
	if(s[i]-1==a):
		a+=1
	elif(s[i]-1==b):
		b+=1
	elif(s[i]-1==c):
		c+=1
print(ans%1000000007)

Submission status: Accepted

Solution code:
n = int(input())
a_array = map(int, input().split())
color = [0, 0, 0]
ans = 1
for a in a_array:
    count = 0
    for i in range(3):
        if color[i] == a:
            if not count:
                color[i] += 1
            count += 1
    ans *= count
    ans %= 1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 1
d = defaultdict(int)
for a in A:
    if a == 0:
        ans *= 3 - d[a]
        d[a] += 1
        continue
    ans *= d[a - 1] - d[a]
    ans %= MOD
    d[a] += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
#import numpy as np

n =int(input())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
p=q=r=0
modnum = 1000000007
answer=1
for i in range(n):
    s=0
    if p == a[i]:
        s += 1
        p += 1
    if q == a[i]:
        s += 1
        if s==1:
            q += 1
    if r == a[i]:
        s += 1
        if s == 1:
            r += 1
#    print(p,q,r,s,a[i])
    answer = (answer * s) % modnum

print(answer)

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:
    if i in color:
        ans *= (color.count(i))
        ans %= mod
        color[color.index(i)] += 1
    else:
        ans = 0
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
R = 0
G = 0
B = 0
output = 1
for i in range(N):
    Rf = 0
    Gf = 0
    Bf = 0
    if A[i]==R:
        Rf = 1
    if A[i]==G:
        Gf = 1
    if A[i]==B:
        Bf = 1
    S = Rf+Gf+Bf
    if Rf==1:
        R+=1
    elif Gf ==1:
        G+=1
    elif Bf==1:
        B+=1
    output *= S
    output = output%1000000007
print(output)

Submission status: Accepted

Solution code:
mod = 1000000007

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(M, a):
    count = M.count(a)
    if count == 0:
        return 0

    for i in range(2, -1, -1):
        if M[i] == a:
            M[i] += 1
            break

    return count


def main():
    N = int(input())
    A = read_list()

    M = [0, 0, 0]
    res = 1

    for a in A:
        res *= f(M, a)
        res %= mod
        if res == 0:
            print(0)
            return

    print(res % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
RGB = [0]*3
ans = 1
for i in A:
    count = 0
    for j in RGB:
        if i == j:
            count += 1
    if count == 0:
        print(0)
        exit()
    RGB[RGB.index(i)] += 1
    ans = (ans * count)% MOD

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xs = list(map(int, input().split()))
A = max(xs)
dp = [0] * (A+1)
MOD = 1000000007

r = 1
zc = 0
for x in xs:
    if x == 0:
        zc += 1
    else:
        r = r * dp[x-1] % MOD
        dp[x-1] -= 1
    dp[x] += 1
if zc == 0 or zc >= 4:
    rr = 0
elif zc == 1:
    rr = 3
else:
    rr = 6
print(r * rr % MOD)
#print(MOD)
#print(115295190)

Submission status: Accepted

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

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

mod = 10**9+7
ans = 1
P = [0, 0, 0]
for a in A:
    c = P.count(a)
    ans = ans*c%mod
    for i in range(3):
        if P[i] == a:
            P[i] += 1
            break
    #print(P)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    color = [-1] * 3
    n = ii()
    A = lmi()
    num = [0] * (max(A) + 10)
    ans = 1
    num[0] = 3
    for i in range(n):
        num[A[i] + 1] += 1
        ans *= num[A[i]]
        num[A[i]] -= 1
        ans %= 1000000007
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
res = 1
amari = 1000000007
rgb = [0, 0, 0]

for a in A:
    cnt = 0
    j = 0
    for i in range(3):
        if rgb[i] == a:
            cnt += 1
            j = i
    rgb[j] += 1
    res *= cnt
    res %= amari

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 1000000007

def main():
	n = int(input())
	a = list(map(int,input().split()))
	h = [-1,-1,-1]
	ans = 1
	for i in range(n):
		# print(i)
		ans = ans*h.count(a[i]-1) % MOD
		for j in range(3):
			if h[j] == a[i]-1:
				h[j] = a[i]
				break
	hn = h.count(-1)
	if hn == 0:
		if h[0] == h[1] and h[1] == h[2]:
			pass
		elif h[0] != h[1] and h[1] != h[2] and h[2] != h[0]:
			pass
		else:
			pass
	elif hn == 1:
		pass
	elif hn == 2:
		pass
	print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())

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

MOD = 1000000007

R = 0
B = 0
G = 0

ans = 1
for a in A:
    #print(a, ans, R)
    count = 0
    if a == R:
        count += 1
    if a == B:
        count += 1
    if a == G:
        count += 1

    ans *= count

    if a == R:
        R += 1
    elif a == B:
        B += 1
    elif a == G:
        G += 1
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
resi = dict()
for i in range(100000+1):
    resi[i] = 0
resi[0] = 3

cnt = 1
for i in range(N):
    if A[i] == 0:
        cnt *= resi[0]
        cnt %= MOD
        resi[0] -= 1
        resi[1] += 1
    else:
        cnt *= resi[A[i]]
        cnt %= MOD
        resi[A[i]] -= 1
        resi[A[i]+1] += 1
    if resi[A[i]+1] > 3 or resi[A[i]] < 0:
        print(0)
        exit()

print(cnt)

Submission status: Accepted

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

num = [0 for _ in range(n)]
count_zero = 0
ans = 1
mod = 1000000007

for i in range(n):
    if a[i] == 0:
        ans *= (3-count_zero)%mod
        count_zero += 1
        num[0] += 1
    else:
        ans *= num[a[i]-1]%mod
        num[a[i]] += 1
        num[a[i]-1] -= 1
print(ans%mod)

Submission status: Accepted

Solution code:
import sys

X = [0,0,0]

n = int(input())
A = [int(x) for x in input().split()]

res = 1
for a in A:
    res = res*X.count(a) % 1000000007
    if X.count(a):
        X[X.index(a)] += 1
    else:
        print(0)
        sys.exit(0)
print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]

C=[0,0,0]
ans=1
for x in A:
    ans *= C.count(x)
    ans%=mod
    for i,a in enumerate(C):
        if a==x:
            C[i]+=1
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
r = 0
g = 0
b = 0

cnt = 1

for i in range(N):
    if A[i] == r:
        if r == g and r == b:
            cnt *= 3
        elif r == g or r == b:
            cnt *= 2
        r += 1
    elif A[i] == g:
        if g == b:
            cnt *= 2
        g += 1
    elif A[i] == b:
        b += 1
    else:
        cnt = 0
        break
        
    cnt %= mod
    
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=[-1,-1,-1]
x=1
for i in a:
  b=0
  f=True
  for j in range(3):
    if d[j]==i-1:
      b+=1
      if f:
        f=False
        d[j]=i
  x*=b
  x%=10**9+7
print(x)

Submission status: Accepted

Solution code:
mod=10**9+7
n,*a=map(int,open(0).read().split())
d=[-1,-1,-1]
ans=1
for x in a:
	ans *= d.count(x-1)
	ans %= mod
	for i in range(3):
		if d[i] == x - 1:
			d[i] = x
			break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
dp = [0 for i in range(n+1)]
if a[0] != 0:
    print(0)
    exit()
dp[0] = 3
r,g,b = 1,0,0
for i in range(1,n):
    if a[i] == r:
        if r == g and g == b:
            dp[i] = dp[i-1]*3
        elif r == g or r == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        r += 1
    elif a[i] == g:
        if g == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        g += 1
    elif a[i] == b:
        dp[i] = dp[i-1]
        b += 1
    else:
        dp[i] = 0
print(dp[n-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=[3]+[0]*(n+1)
m=10**9+7
c=1
for i in a:
    s[i+1]+=1
    c=(c*s[i])%m
    s[i]-=1
    if s[i]<0:
        print(0)
        break
else:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    ans=1
    C=[0]*(n+1)
    C[0]=3
    for a in A:
        ans*=C[a]
        ans%=MOD
        C[a]-=1
        C[a+1]+=1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
INF=10**9+7
n=int(input())
a_list=list(map(int,input().split()))
l=[0,0,0]
ans=1
for i in range(n):
    c=0
    for j in l:
        if j==a_list[i]:
            c+=1
    ans=(ans*c)%INF
    for j in range(3):
        if l[j]==a_list[i]:
            l[j]+=1
            break
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007


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


ans = 1
counter = [0, 0, 0]
for i in range(n):
    index = list()
    for j in range(len(counter)):
        if counter[j] == A[i]:
            index.append(j)

    ans *= len(index)
    ans = ans % MOD
    if len(index) == 0:
        break
    else:
        counter[index[0]] += 1

print(ans)

Submission status: Accepted

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

mod = 1000000007

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

print(ans%mod)

Submission status: Accepted

Solution code:
#%%
n = int(input())
s = list(map(int, input().split()))
inf =  1000000007

a, b, c = 0, 0, 0
ans = 1

for i in range(n):
	tmp = [a, b, c].count(s[i])
	ans *= tmp
	ans %= 1000000007
	if s[i] == a:
		a += 1
	elif s[i] == b:
		b += 1
	else:
		c += 1
	

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 10 ** 9 + 7
N = int(input())
As = list(map(int, input().split()))

counts = [-1, -1, -1]
ans = 1

for a in As:
    ct = Counter(counts)
    ans *= ct[a-1]
    ans %= MOD
    for i in range(3):
        if counts[i] == a-1:
            counts[i] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
a=int(input())
b=list(map(int,input().split()))
c=[0,0,0]
ans=1
mod=1000000007
for i in b:
  d=0
  for j in c:
    if i==j:
      d+=1
  if d==0:
    print(0)
    exit()
  else:
    ans=ans*d%mod
    for j in range(3):
      if i==c[j]:
        c[j]+=1
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())
MOD = 1000000007

next = [0,0,0]
ans = 1

for ai in a:
    cnt = next.count(ai)
    if cnt == 0:
        ans = 0
        break
    else:
        idx = next.index(ai)
        next[idx] += 1
        ans *= cnt
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def main():
    # input
    MAX = 1000000007
    n = int(input())
    a = list(map(int, input().split()))

    li = [0 for _ in range(100002)]
    li[-1] = 3

    ans = 1
    cap = [0, 0, 0]
    for i in a:
        ans *= li[i-1]-li[i]
        ans = ans%MAX
        li[i] += 1
    print(ans)


    # calc


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def p_e():
    n = int(input())
    *A, = map(int, input().split())
    mod = 1000000007
    dp = [0] * 3
    ans = 1
    for a in A:
        num = 0
        flg = True
        # print(dp)
        for j in range(3):
            if dp[j] == a:
                if flg:
                    dp[j] += 1
                    flg = False
                num += 1
        ans *= num
        ans %= mod

    print(ans)
    
p_e()

Submission status: Accepted

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

c = [0, 0, 0]

ans = 1
for i in range(n):
    count = 0
    for _c in c:
        if a[i] == _c:
            count += 1

    ans = ans * count % 1000000007
    if c[0] == a[i]:
        c[0] += 1
    elif c[1] == a[i]:
        c[1] += 1
    else:
        c[2] += 1

print(ans)