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:

n = int(input())
num = [ int(v) for v in input().split() ]
counter = [3] + [ 0 for i in range(n) ]
ans = 1
mod = 10**9+7
for i in num:
    ans *= counter[i]
    ans %= mod
    counter[i] -= 1
    counter[i+1] += 1

print(ans)

Submission status: Accepted

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

c = [0]*3

a = 1

for i in A:
    if c.count(i) != 0:
        a *= c.count(i)
        c[c.index(i)] += 1
    
    else:
        print(0)
        break
else:
    print(a%1000000007)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 3
num = 0
ans = 1

for i in range(n):
	if cnt.count(a[i])  == 0:
		ans = 0
		break
	else:
		ans = (ans * cnt.count(a[i])) % 1000000007
		cnt[cnt.index(a[i])] += 1
	num = 0

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
ans = 1
# index: 同じ帽子をかぶっている人数
# value: 色の数
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: Accepted

Solution code:
N = int(input())

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

hats = [0, 0, 0]


ans = 1

for i in range(N):
    same_color = num_list[i]
    if same_color not in hats:
        print(0)
        break
    cand_num = hats.count(same_color)
    ans *= cand_num
    ans = ans % 1000000007
    hats[hats.index(same_color)] += 1
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = max(a)
mod = 1000000007
memo = [[] for i in range(m+1)]
d = {-1: 3}
ans = 1
for ai in a:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1
    if ai - 1 in d:
        memo[ai].append(d[ai-1])
    else:
        ans  = 0
for l in memo:
    i = 0
    for li in l:
        ans = ans * (li - i) %  mod
        i += 1
print(ans)

Submission status: Accepted

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

ans, C, MOD = 1, [-1, -1, -1], 1000000007
for a in A:
    match = sum([1 for c in C if c + 1 == a])
    if match == 0:
        print(0)
        exit()
    else:
        ans = (ans * match) % MOD
        for i in (0, 1, 2):
            if C[i] + 1 == a:
                C[i] += 1
                break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
cnt = [0]*(N+1)
ans = 1
mod=10**9+7
for i in range(N):
  if A[i]!=0:
    ans *=cnt[A[i]-1]-cnt[A[i]]
    cnt[A[i]]+=1
  else:
    ans *=(3-cnt[A[i]])
    cnt[A[i]]+=1
print(ans%mod)

Submission status: Accepted

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

    x = 0
    y = 0
    z = 0
    ans = 1
    for n in A:
        T = 0
        found = False
        for m in [x, y, z]:
            if n == m:
                T += 1
        ans *= T

        if x == n:
            x += 1
            continue
        if y == n:
            y += 1
            continue
        if z == n:
            z += 1
            continue
    
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    x = 0
    y = 0
    z = 0
    ans = 1
    for n in A:
        T = 0
        found = False
        for m in [x, y, z]:
            if n == m:
                T += 1
        ans *= T
        ans %= mod

        if x == n:
            x += 1
            continue
        if y == n:
            y += 1
            continue
        if z == n:
            z += 1
            continue
    
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
inf = 1000000007

ans = 1
cap = [0, 0, 0]
for i in range(N):
    tmp = 0
    for j in range(3):
        if cap[j] == A[i]:
            tmp += 1
    for j in range(3):
        if cap[j] == A[i]:
            cap[j] += 1
            break
    ans *= tmp
    ans %= inf

print(ans)

Submission status: Accepted

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

mod = 10**9+7

ans = 3
if A[0]!=0: ans = 0
dp = [1,0,0]
for a in A[1:]:
    ans *= dp.count(a)
    ans %= mod
    if ans == 0: break
    dp[dp.index(a)] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
D = defaultdict(int)
D[0] = 3

ans = 1
for a in A:
    ans *= D[a]
    ans %= MOD
    D[a] -= 1
    D[a + 1] += 1

print(ans % MOD)

Submission status: Accepted

Solution code:
# atcoder : python3 (3.4.3)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7

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

ans = 1
cnt = [3]+[0]*(N)

for i in range(N):
    ans *= cnt[A[i]]
    ans %= mod
    cnt[A[i]] -= 1
    cnt[A[i]+1] += 1

print(ans)

Submission status: Accepted

Solution code:
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=my_index(b[-1],a[i])
    if k==-1:
        print(0)
        break
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)

Submission status: Accepted

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

C = [3] + [0 for i in range(N)]

ans = 1
for a in A:
  ans *= C[a]
  ans %= MOD
  C[a] -= 1
  C[a+1] += 1
print(ans)

Submission status: Accepted

Solution code:
_,a=open(0)
c=1
d=[3]+[0]*10**6
for a in a.split():a=int(a);c=c*d[a]%(10**9+7);d[a]-=1;d[a+1]+=1
print(c)

Submission status: Accepted

Solution code:
n=int(input())
#tempt

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: Accepted

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

Submission status: Accepted

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

dp = [0] * (N + 1)
dp[0] = 3

ans = 1
for a in A:
    ans *= dp[a]
    ans %= MOD
    dp[a] -= 1
    dp[a + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    B = [0, 0, 0]
    T = [0]*N
    for i in range(N):
        # print(B)
        m = -1
        for j in range(3):
            if A[i]==B[j]:
                T[i] += 1
                m = j
        if m != -1:
            B[m] += 1
    # print(T)

    ans = reduce(lambda x,y: x*y % 1000000007, T)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from string import digits
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]
        res = res * rgb.count(cur) % MOD
        if rgb[0] == cur:
            rgb[0] += 1
        elif rgb[1] == cur:
            rgb[1] += 1
        elif rgb[2] == cur:
            rgb[2] += 1
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(input().split())
l1 = [int(i) for i in l]
ans = 1
mod = 10**9+7
ch = [0]*3
for i in range(n):
  if l1[i] in ch:
    ans = ans * ch.count(l1[i]) % mod
    
    k = ch.index(l1[i])
    ch[k] += 1
    
  else:
    print(0)
    exit()
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(int(x) for x in input().split())
mod = 1000000007

rgb = [0,0,0]
sum = 1
for a in A:
    if(rgb.count(a)!=0):
        sum = sum * rgb.count(a) % mod
        rgb[rgb.index(a)]+=1
    else:
        print(0)
        exit()
print(sum)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    zero = 3
    ans = 1
    ls = [0 for _ in range(N)]
    mod = 1000000007
    for i in A:
        if i == 0:
            ans = (ans*zero)%mod
            zero -= 1
            ls[i] += 1
        else:
            ans = (ans*(ls[i-1]-ls[i]))%mod
            ls[i] +=1

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
c = [-1,-1,-1]
a = 1
for i in map(int,input().split()):
  co = c.count(i-1)
  if co == 0:
    print(0)
    exit()
  a = a * co % 1000000007
  c[c.index(i-1)] = i
print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
data = [[0]*3 for i in range(n+1)]
mod = 10**9+7
#data[i][0] => max: data[i][1] =>  middle: data[i][2] => min:
ans = 1
for i in range(n):
    tmp = data[i]
    ans *= tmp.count(a[i])
    ans %= mod
    for j in range(3):
        data[i+1][j] = data[i][j]
    for j in range(3):
        if data[i][j] == a[i]:
            data[i+1][j] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
now_colors = [-1, -1, -1]  # 赤色, 青色, 緑色
ans = 1
for i in range(N):
    candidate_count = 0
    flag = [False]*3
    for j in range(3):
        if A[i]-1 == now_colors[j]:
            candidate_count += 1
            flag[j] = True
    for k in range(3):
        if flag[k]:
            now_colors[k] += 1
            break
    ans *= candidate_count % mod
print(ans % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
C = [0] * 100001
C[0] = 3
答 = 1
for x in A:
  答 *= C[x]
  答 %= MOD
  C[x] -= 1
  C[x+1] += 1
print(答)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 1
hats = [0, 0, 0]
 
for a in A:
    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:
import sys
sys.setrecursionlimit(10 ** 7)

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

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Submission status: Accepted

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

col_lst = [0 , 0 , 0]
ans = 1

for i in range(n):
    tmp = lst[i]
    val = col_lst.count(tmp)
    if val == 0:
        print(0)
        exit()
    else:
        ans = (ans * val) % mod
        col_lst[col_lst.index(tmp)] += 1
print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 1
s = [0] * 3

for i in range(n):
    ans *= len([0 for x in s if x == a[i]])
    if ans == 0: break
    ans %= MOD
    for j in range(3):
        if s[j] == a[i]:
            s[j] += 1
            break

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    _ = int(input())
    A = [int(i) for i in input().split()]
    rgb = [0, 0, 0]
    ans = modint(1)
    for a in A:
        if rgb[0] == a:
            if rgb[0] == rgb[1] and rgb[0] == rgb[2]:
                ans *= 3
            elif rgb[0] == rgb[1]:
                ans *= 2
            rgb[0] += 1
        elif rgb[1] == a:
            if rgb[1] == rgb[2]:
                ans *= 2
            rgb[1] += 1
        elif rgb[2] == a:
            rgb[2] += 1
        else:
            return print(0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
def main():
    N = int(input())
    A = list(map(int,input().split()))
    R = 1000000007

    Ans = 1
    P = [0, 0, 0]
    for Ai in A:
        Count = 0
        for i, Pi in enumerate(P):
            if Ai == Pi:
                if Count == 0:
                    P[i] += 1
                Count += 1
        Ans = (Ans * Count) % R

    print(Ans)

             
 

        
 
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

    flag = [0 for _ in range(100000)]
    res = 1
    for i in range(n):
        ta =  a[i]
        if ta == 0:
            res *= 3 - flag[0]
            res %= mod
        else:
            fta1 = flag[ta-1]
            fta = flag[ta]
            if fta1 == 0:
                return 0
            res *= fta1 - fta
            res %= mod
        flag[ta] += 1
        if flag[a[i]] > 3:
            return 0
    return res 

print(main())

Submission status: Accepted

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


cache = [ 0 for _ in range(N+1)] 

cache[0] = 3
amount = 1
mod = 1000000007
for i in range(N):
    need_hat = An[i]
    amount = amount * cache[need_hat] % mod
    cache[need_hat] -= 1
    cache[need_hat+1] += 1
print(amount)

Submission status: Accepted

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

num_table = [0] * N
ans = 1
for i in range(N):
    if A[i] == 0:
        ans *= (3 - num_table[A[i]])
        num_table[A[i]] += 1
        continue
    ans *= (num_table[A[i] - 1] - num_table[A[i]])
    ans %= mod
    num_table[A[i]] += 1

print(ans)

Submission status: Accepted

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

count = {-1: 3}
ans = 1
mod = 10 ** 9 + 7
for x in data:
  val = count.get(x-1, 0) - count.get(x, 0) 
  ans = (ans * val) % mod
  count[x] = count.get(x, 0) + 1
print (ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
    MOD = 1000000007
    N, *a_l = map(int, open(0).read().split())
    t_l = [3] + [0 for _ in range(N+1)]
    ans = 1

    for a in a_l:
        ans = t_l[a] * ans % MOD
        t_l[a] -= 1
        t_l[a+1] += 1
    
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 1000000007

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

cnts = [3 if i == 0 else 0 for i in range(N + 1)]

res = 1
for a in A:
    res = res * cnts[a] % MOD
    cnts[a] -= 1
    cnts[a + 1] += 1

print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=0
b=0
g=0
ans=1
for i in range(n):
    num=0
    if r==a[i]:
        num+=1
    if g==a[i]:
        num+=1
    if b==a[i]:
        num+=1
    ans*=num

    if r==a[i]:
        r+=1
    elif g==a[i]:
        g+=1
    elif b==a[i]:
        b+=1
print(ans%1000000007)

Submission status: Accepted

Solution code:
MOD = 1000000007
N = int(input())
A = [int(i) for i in input().split()]
count = [0]*N
dp = [0]*N
if A[0] != 0:
    print(0)
    exit()
dp[0] = 3
count[0] += 1
for i, a in enumerate(A[1:]):
    if a == 0:
        dp[i+1] = dp[i]*(3-count[a])
    elif count[a] >= count[a-1]:
        print(0)
        exit()
    else:
        dp[i+1] = dp[i]*(count[a-1]-count[a])
    count[a] += 1
    dp[i+1] %= MOD
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

countA = [0]*(max(A)+1)
ans = 1
mod = 10**9 + 7
for i in range(N):
    if A[i] == 0:
        ans *= (3 - countA[A[i]])
    else:
        ans *= (countA[A[i]-1] - countA[A[i]])
    countA[A[i]] += 1
    ans %= mod
print(max(ans, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
c=1
d=[0]*3
for b in a:
  c=c*sum(t==b for t in d)%(10**9+7)
  for i,t in enumerate(d):
    if t==b:
      d[i]+=1
      break
print(c)

Submission status: Accepted

Solution code:
n=int(input())
it=list(map(int,input().split()))
mod=1000000007
#dp=[[0,0,0] for i in range(n+1)]
#dp[-1]=[1,1,1]
#col=[0 for i in range(n)]
#fe=[]
cu=0
tot=1
ss=[0 for i in range(n+1)]
ss[-1]=3

for i in range(n):
    tot*=(ss[it[i]-1]-ss[it[i]])
    tot%=mod
    ss[it[i]]+=1
    
    
        
        
                
print(tot)
#print(tot%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = [0] * (N+1)
C[0] = 3

ans = 1
for a in A:
    ans *= C[a]
    ans %= MOD
    C[a] -= 1
    C[a+1] += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 1
cnt = [0, 0, 0]

for i in a:
    ans *= cnt.count(i)
    ans %= mod
    if i not in cnt:
        print(0)
        exit()
    ind = cnt.index(i)
    cnt[ind] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 1
cnt = [0, 0, 0]

for i in range(n):
    ans *= cnt.count(a[i])
    if a[i] not in cnt:
        print(0)
        exit()
    ind = cnt.index(a[i])
    cnt[ind] += 1

print(ans % mod)

Submission status: Accepted

Solution code:
# ref) https://atcoder.jp/contests/sumitrust2019/submissions/8731837

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

MOD = 10 ** 9 + 7

ans = 1
X = [0, 0, 0]
for a in A:
    c = X.count(a)
    ans = ans * c % MOD
    
    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:
n=int(input())
lists=list(map(int,input().split()))
counter=1
uselist=[0,0,0]
for j in range(n):
    human=lists[j]
    sub=0
    for p in range(3):
        if uselist[p]==human:
            sub+=1
    for q in range(3):
        if uselist[q]==human:
            uselist[q]+=1
            break
    counter=counter*sub
    counter=counter%(10**9+7)
if lists[0]==0:
    print(counter)
else:
    print(0)

Submission status: Accepted

Solution code:
input()
dp,M,r=[3]+[0]*10**6,10**9+7,1
for x in map(int, input().split()):
    r=r*dp[x]%M
    dp[x]-=1
    dp[x+1]+=1
print(r)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
rgb=[0,0,0]

res=1
for each in a:
  res*=rgb.count(each)
  if rgb[0] == each: rgb[0] += 1
  elif rgb[1] == each: rgb[1] += 1
  elif rgb[2] == each: rgb[2] += 1
  res %= 1000000007
print(res)

Submission status: Accepted

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


def main():
    mod = 1000000007
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0, 0, 0]
    ans = 1
    for a in A:
        ans = ans * cnt.count(a) % mod
        for j in range(3):
            if cnt[j] == a:
                cnt[j] = a+1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N=int(input())
a=list(map(int,input().split()))
ans=1
l=[0,0,0]
mod=10**9+7
for i in range(N):
  ans*=(l.count(a[i]))
  if a[i] not in l:
    print(0)
    sys.exit()
  index=l.index(a[i])
  l[index]+=1
print(ans%mod)

Submission status: Accepted

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

N = int(input())
A = [int(i) for i in input().split()]
MOD = 10**9 + 7
answer = 1
color = [0]*3

# answer *= A[i]における分岐の数
for i in A:
    answer = (answer * color.count(i)) % MOD
    for j,x in enumerate(color):
        if x == i:
            color[j] += 1
            break

print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 1
rgb = [0,0,0]
for x in a:
    ans *= rgb.count(x)
    if rgb[0] == x: rgb[0] += 1
    elif rgb[1] == x :rgb[1] += 1
    elif rgb[2] == x :rgb[2] += 1
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = [0 for i in range(max(A)+2)]
ans = 1
L[0] = 3
p = 10 ** 9 + 7
for i in range(N):
  ai = A[i]
  ans *= (L[ai] - L[ai + 1])
  ans = ans % p
  L[ai + 1] += 1
print(ans)

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()))
mod = 1000000007
cnt = [3 if i == 0 else 0 for i in range(N + 1)]
ans = 1

for a in A:
    ans = ans * cnt[a] % mod
    cnt[a] -= 1
    cnt[a+1] += 1

print(ans)

Submission status: Accepted

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


def main():
    mod = 1000000007
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [[0, 0, 0] for i in range(N+1)]
    ans = 1
    for i in range(N):
        a = A[i]
        ans = ans * cnt[i].count(a) % mod
        for j in range(3):
            cnt[i+1][j] = cnt[i][j]
        for j in range(3):
            if cnt[i][j] == a:
                cnt[i+1][j] = a+1
                break
    print(ans)


if __name__ == '__main__':
    main()