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:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate
MOD = 10**9 + 7


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


N = read_a_int()
A = read_ints()
# 重要な考察
# 1, i番目の人がかぶれる帽子は[0,i)における帽子の内訳の中で,A_iに数が等しいものである
# 2, i番目における各帽子の個数は(色はわからないけど)確定できる. ∵A_iに等しい個数の帽子がかぶれるということとは、次はその個数+1個の帽子があるはず

# よってAi、通りの数を取得ansに掛け算。さらに各種帽子の個数を更新してA{i+1}の処理に映れば良い

ans = 1
c = [0, 0, 0]
for a in A:
    ans *= c.count(a)  # 通りの数に加算
    for i in range(3):
        if a == c[i]:
            c[i] += 1
            break
    if ans > MOD:
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
ans=1
from collections import Counter
c=Counter()
c[0]+=3
for i in a:
    ans*=c[i]
    if ans==0:
        break
    c[i]-=1
    c[i+1]+=1
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 1000000007
ans = 1
l = []
for i in range(n):
  if a[i] == 0:
    l.append(0)
    ans = ans*(4-len(l))%mod
  else:
    id = -1
    count = 0
    for j in range(len(l)):
      if l[j] == a[i] - 1:
        count += 1
        id = j
    if id == -1:
      ans = 0
      break
    ans = (ans*count)%mod
    l[id] = a[i]
  if ans == 0:
    break
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import defaultdict
from bisect import *
mod = 10**9+7

N = int(input())
A = list(map(int, input().split()))
cnt = [0]*3
ans = 1
for i, x in enumerate(A):
    T = len([c for c in cnt if c == x])
    for i, c in enumerate(cnt):
        if c == x:
            cnt[i] += 1
            break
    ans = ans * T % mod
print(ans)

Submission status: Accepted

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

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:
        s = 0
        for k in d:
            if k == i:
                s += 1
        if not s:
            print(0)
            return
        ans *= s
        ans %= mod
        for k in range(3):
            if d[k] == i:
                d[k] += 1
                break
    print(ans)
    return

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

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
import sys
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
count=1
lst=[0,0,0]
for a in A:
    data=[i for i in range(3) if lst[i] == a]
    if not data:
        count=0
        break
    count*=len(data)
    count%=mod
    i=data[0]
    lst[i]+=1
print(count)

Submission status: Accepted

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

ans = 1
dp = [0]*3
for a in A:
    ans = ans*dp.count(a) % MOD
    try:
        dp[dp.index(a)] += 1
    except ValueError:
        break
print(ans)

Submission status: Accepted

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

ans = 1
dp = [0]*3
for a in A:
    cnt = 0
    for i in range(3):
        if a == dp[i]:
            cnt += 1
    for i in range(3):
        if a == dp[i]:
            dp[i] += 1
            break
    ans = ans*cnt % MOD
print(ans)

Submission status: Accepted

Solution code:
input()
v = [0,0,0]
ans = 1
MOD = 1000000007
for a in map(int,input().split()):
    c = v.count(a)
    ans *= c
    ans %= MOD
    if ans == 0:
        break
    v[v.index(a)] += 1
print(ans)

Submission status: Accepted

Solution code:
input()
v = [0,0,0]
ans = 1
MOD = 1000000007
for a in map(int,input().split()):
    c = v.count(a)
    ans *= c
    ans %= MOD
    if ans == 0:
        break
    v[v.index(a)] += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pytho3
n = int(input())
a = list(map(int,input().split()))
# ３種類の値をもち、自分より前に同じ色の人がa[i]となる組み合わせ
# コーナーケースとして、全部同じ色なら3通り、あとは*6したらいい
# n<=10**5
# 先頭を色１、次にa[i] == 0になった点を色2,3にしてしていい。前から埋める
# 前から見ていって、それぞれの色の今の人数をcolorとして
# color.count(a[i]) == 2　ならans *= 2, ==3 ans *= 3
# 2ケースのみRE
mod = 10**9 + 7
if a == list(range(n)): print(3)
else:
  k = 0
  ans = 6
  color = [0,0,0]
  for person in range(n):
    #print(color,person)
    bit = 0#すでにcolor == a[i]が出てきているか?
    if a[person] == 0:
      if k == 3:#REになるケース
        print(0)
        exit()
      color[k] = 1
      k += 1
      continue
    for num in range(3):
      if color[num] == a[person]:
        bit += 1
        if bit == 1:
          color[num] += 1
      if num == 2: 
        ans *= bit
        ans = ans % mod
  print(ans)

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    cnt = [3] + [0]*n
    res = 1
    for i in a:
        if cnt[i] == 3:
            res *= 3
        if cnt[i] == 2:
            res *= 2
        if cnt[i] == 0:
            res *= 0
        cnt[i] -= 1
        cnt[i+1] += 1
        res %= mod
    print(res)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    cnt = [3] + [0]*n
    res = 1

    for i in a:
        res *= cnt[i] % mod
        cnt[i] -= 1
        cnt[i+1] += 1
        res %= mod

    print(res)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Count = {x:0 for x in range(0, n)}

mod = 10**9+7
ans = 1

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

print(ans)
# print(Count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy
input = sys.stdin.readline
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N = int(input())
A = LI()
c =[0,0,0]
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[i] = c.count(A[i])
    if cnt[i] == 0: break
    c[c.index(A[i])] += 1
ans = 1
for i in range(N):
    ans = (ans * cnt[i]) % MOD
print (ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
_LI = lambda : [int(x)-1 for x in input().split()]
N = int(input())
A = LI()


c =[0,0,0]
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[i] = c.count(A[i])
    if cnt[i] == 0:
        print (0)
        exit (0)
    for j in range(3):
        if c[j] == A[i]:
            c[j] += 1
            break
ans = 1
for i in range(N):
    ans = (ans * cnt[i]) % MOD
print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  if A[i] not in color:
    ans = 0
    break
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  if A[i] not in color:
    ans = 0
    break
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

n=int(input())
A=[int(i) for i in input().split()]
ans=1
mod=10**9+7
C=[0,0,0]
for i in range(n):
  cur=A[i]
  ct=0
  Chk=True
  for i,c in enumerate(C):
    if cur==c:
      ct+=1
      if Chk:
        C[i]+=1
        Chk=False
  ans=(ans*ct)%mod
  
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
C = {i:0 for i in range(N)}
C[-1] = 3
cnt = 1
for i in range(N):
    a = A[i]
    cnt = (cnt*(C[a-1]-C[a]))%p
    C[a] += 1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    N = INT()
    A = LI()
    RGB = [0,0,0]
    answer = 1
    MOD = 10**9+7

    for i in range(N):
        if RGB.count(A[i]) == 0:
            print(0)
            return

        answer *= RGB.count(A[i])
        answer %= MOD
        for j in range(3):
            if RGB[j] == A[i]:
                RGB[j] += 1
                break

    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
data = [0, 0, 0]
ans = 1
for x in a:
    y = 0
    t = True
    for i in range(3):
        if data[i] == x:
            y += 1
            if t:
                t = False
                data[i] += 1
    ans *= y
    ans %= mod

print(ans)

Submission status: Accepted

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

li = [0 for i in range(N)]
ans = 1

for i in range(N):
    a = A[i]
    if a>0:
        ans *= min(3-li[a],li[a-1]-li[a])
        ans %= 10**9+7
        li[a] += 1
    elif a==0:
        ans *= 3-li[0]
        li[a] += 1
    # print(i,ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))
ans = 1
cnt = [0] * 3
mod = 10**9+7
for i in range(N):
	opt = 0
	cond = 1
	for j in range(3):
		if cnt[j] == P[i]:
			opt += 1
			if cond:
				cnt[j] += 1
				cond = 0

	ans *= opt
	ans %= mod

ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  if c==0:
    print(0)
    exit()
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
rbg = [-1, -1, -1]
ans = 1
mod = 10 ** 9 + 7

for A in a:
    ans *= rbg.count(A - 1)
    ans %= mod
    for i in range(3):
        if rbg[i] == A - 1:
            rbg[i] = A
            break

print(ans)

Submission status: Accepted

Solution code:
N  = int (input())
nums = list(map(int, input().split(" ")))
colors = [0,0,0]
ans = 1
MOD = 10 ** 9 + 7
for num in nums:
    cot = 0
    ind = -1
    for i in range(3):
        if colors[i] == num:
            ind = i
            cot += 1
    colors[ind] += 1
    ans *= cot
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 1000000007
    
    color = [0] * N
    can_use = [0] * (N + 1)
    can_use[0] = 3
    for i in range(N):
        color[i] = can_use[A[i]]
        can_use[A[i]] -= 1
        can_use[A[i] + 1] += 1
    ans = 1
    for c in color:
        ans = ans * c % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

col=[0,0,0]
res=1

for ai in a:
    cnt=0
    for i in range(3):
        if col[i]==ai:
            if cnt==0:
                col[i]=col[i]+1

            
            cnt+=1
            
    
    res=(res*cnt)%1000000007

print(res)

Submission status: Accepted

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

def count(n, list1):
    num0 = list1.count(0)
    statuslist = []
    answer = 1
    if num0 >= 4:
        return 0
    else:
        for i in range(len(list1)):
            if list1[i] == 0:
                    statuslist.append(0)
            else:
                pos = statuslist.count(list1[i]-1)
                answer *= pos
                try:
                    statuslist.remove(list1[i]-1)
                except ValueError:
                    return answer
                statuslist.append(list1[i])
        if num0 == 2 or num0 == 3:
            answer *= 6
        elif num0 == 1:
            answer *= 3  
        return (answer % 1000000007)
    # else:
    #     return 3
        

print(count(n, list1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N = int(input())
    a = list(map(int,input().split()))
    d = defaultdict(int)
    ans = 1
    d[0] += 3
    MOD = 1000000007
    for num in a:
        ans *= d[num]
        ans %= MOD
        d[num] -= 1
        d[num+1] += 1
    
    print(ans)

if __name__ == "__main__":
    main()

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)
    for j in range(3):
        if cnt[j] == i:
            cnt[j] += 1
            break
    ans %= mod
print(ans)

Submission status: Accepted

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

#R,B,Gの順に埋めていく
#R,B,Gの現在の数を保存する
cnt={'R':0,'B':0,'G':0}
ans=1
for i in range(n):
    count=0
    edi=0
    for j in 'RBG':
        if cnt[j]==a[i]:
            count+=1
            if edi==0:
                cnt[j]+=1
                edi=1
    ans*=count
print(ans%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
d=defaultdict(int)
n=int(input())
a=list(map(int,input().split()))
ans=1
mod=10**9+7
d[-1]=3
for i in a:
  ans*=d[i-1]
  ans%=mod
  d[i-1]-=1
  d[i]+=1
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

def main():
    N,*A=map(int, open(0).read().split())
    C=[0]*(N+1)
    C[-1]=3
    ans=Fp(1)
    for a in A:
        ans*=C[a-1]
        C[a-1]-=1
        C[a]+=1
    print(ans)

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:
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)
    d[-1] = 3
    mt = 1
    for v in a:
        mt *= d[v-1]
        mt %= mod
        d[v-1] -= 1
        d[v] += 1
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

cnt = [0] * (n + 1)
cnt[-1] = 3

ret = 1
for x in a:
    ret = ret * cnt[x - 1] % mod
    cnt[x - 1] -= 1
    cnt[x] += 1

print(ret)

Submission status: Accepted

Solution code:
N = int(input())
ans = 1
*a, = map(int, input().split())
mod = 10**9+7

l = [[0,0,0] for _ in range(N+1)]
r, g, b = 0, 0, 0

for i, j in enumerate(a):
    if i:
        if j==0:
            if g==0:
                g += 1
            else:
                b += 1
        else:
            if r==j:
                r += 1
            elif g==j:
                g += 1
            elif b==j:
                b += 1
    else:
        r += 1
     
    l[i+1][0] = r
    l[i+1][1] = g
    l[i+1][2] = b

ans = 1
for i,j in zip(a, l):
    ans *= j.count(i)
    ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
dic=collections.defaultdict(int)
dic[-1]=3
ans=1
for i in range(n):
  dic[arr[i]]+=1
  ans*=dic[arr[i]-1]
  ans%=mod
  dic[arr[i]-1]-=1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
n = int(readline())
A = map(int, readline().split())
mod = 1000000007

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

Submission status: Accepted

Solution code:
p = 1000000007
n = int(input())
A = list(map(int, input().split()))

ans = 1
cnt = [3 if i == 0 else 0 for i in range(n+1)]

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

Submission status: Accepted

Solution code:
p = 1000000007
n = int(input())
A = list(map(int, input().split()))

ans = 1
cnt = [3 if i == 0 else 0 for i in range(n+1)]

for a in A:
    ans *= cnt[a]
    ans %= p
    if ans == 0:
        break
    cnt[a] -= 1
    cnt[a+1] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
res = 1
cnt = [0,0,0]
for i in range(n):
    res *= cnt.count(a[i])
    res %= mod
    if res == 0: break
    cnt[cnt.index(a[i])] += 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        last_cnt=3
        tmp = last_cnt - d[num]
    else:
        last_cnt=d[num-1]
        tmp = last_cnt - d[num]

        if tmp == 0:
       #     tmp=1
            ans=0
    ans*=tmp
    ans%=1000000007
    d[num]+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        last_cnt=3
    else:
        last_cnt=d[num-1]

    tmp = last_cnt - d[num]
    if tmp < 0:
        tmp=1
    ans*=tmp
    ans%=1000000007
    d[num]+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        last_cnt=3
    else:
        last_cnt=d[num-1]

    tmp = last_cnt - d[num]
#    if tmp <= 0:
#        tmp=1
    ans*=tmp
    ans%=1000000007
    d[num]+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        ans*= (3 - d[0])
    else:
        ans*= (d[num-1] - d[num])

    ans%=1000000007
    d[num]+=1

print(ans)

Submission status: Accepted

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

ans = 1
rgb = [0, 0, 0]
for i in range(N):
    c = rgb.count(A[i])
    if c == 0:
        ans = 0
        break
    p = rgb.index(A[i])
    ans *= c
    rgb[p] += 1

print(ans % M)

Submission status: Accepted

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

MOD = 1000000007

dic = {}
dic[0] = 3
for i in range(1,n+1):
    dic[i] = 0

ans = 1
for i in range(n):
    ans = ans * dic[a[i]] % MOD
    dic[a[i]] -= 1
    dic[a[i] + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt={'R':0,'B':0,'G':0}
ans=1
for i in range(n):
    count=0
    num=0
    for j in 'RBG':
        if cnt[j]==a[i]:
            count+=1
            if num==0:
                cnt[j]+=1
                num=1
    ans*=count
print(ans%(10**9+7))

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()]
    from collections import defaultdict
    d = defaultdict(int)
    ans = modint(0)
    for a in A:
        d[a] += 1
        if (a != 0 and d[a-1] < d[a]) or 3 < d[a]:
            return print(0)
        if a == 0:
            if d[a] == 1:
                ans += 1
            elif d[a] == 2:
                ans *= 2
            continue
        if d[a] == 1:
            ans *= d[a-1]
        elif d[a] == 2:
            ans *= d[a-1] - 1

    print((ans*3))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
hat = [0, 0, 0]
MOD = 10 ** 9 + 7
answer = 1
for i in range(N):
    x = hat.count(A[i])
    if x == 0:
        answer = 0
    else:
        answer *= x
        j = hat.index(A[i])
        hat[j] += 1
        answer %= MOD

print(answer%MOD)
# 30

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
hat = [0, 0, 0]
MOD = 10 ** 9 + 7
answer = 1
for i in range(N):
    x = hat.count(A[i])
    if x == 0:
        answer = 0
    else:
        answer *= x
        j = hat.index(A[i])
        hat[j] += 1

print(answer%MOD)
# 30

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
x = 0
y = 0
z = 0
ans = 1
for i in range(n):
  a = A[i]
  ans *= int(a==x) + int(a==y) + int(a==z)
  if a == x:
    x += 1
  elif a == y:
    y += 1
  elif a == z:
    z += 1
  else:
    print(0)
    exit()
print(ans%(10**9+7))

Submission status: Accepted

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

mod = 1000000007
N = int(input())
AA = list(map(int, input().split()))

num = [0,0,0]
ans = 1
for i in AA:
	f = False
	cnt = 0
	for j in range(3):
		if(num[j] == i):
			if f==False : 
				num[j] += 1
				f=True
			cnt += 1
	ans = (ans * cnt) % mod
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] 
    if ans == 0:
        break
    cnt[a] -= 1
    cnt[a+1] += 1

print(ans%MOD)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
C = [0, 0, 0]  # 同じ帽子をかぶっている人数　降順
B = 10 ** 9 + 7
ans = 1
for i in range(N):
    if A[i] in C:
        ans *= C.count(A[i])
        C[C.index(A[i])] += 1
    else:
        ans = 0
        break
print(ans % B)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
num = [0 for i in range(3)]
suma = 1
mod = 10**9+7
for i in A:
    suma = (suma*num.count(i))%mod
    if num[0] == i:
        num[0] += 1
    elif num[1] == i:
        num[1] += 1
    else:
        num[2] += 1
print(suma)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

ctr = [0] * (n + 1)
ctr[-1] = 3

ret = 1
for x in a:
    ctr[x] += 1
    ret = ret * ctr[x - 1] % mod  # ctr[x - 1]: 同じ色の帽子の候補者数
    ctr[x - 1] -= 1

print(ret)

Submission status: Accepted

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

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

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:
N = int(input())
A = list(map(int,input().split()))

MOD = 1000000007

#色ごとの人数
C=[0,0,0]
ans=1
for a in A:
    #人数が一致する色がなければOUT
    found=False
    count=C.count(a)
    if count==0:
        print(0)
        exit()
    #適当に1人足す
    C[C.index(a)]+=1
    #今見ている人の色の可能性はcount種類
    ans=ans*count%MOD

print(ans)