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:
# similar to problem if n person are arranged in a row and have 3 different hats to wear
# no of ways of wearing hats so that every adjacent person wears different hats
# so ith person cannot wear more than 3 no of different ways
mod = 10**9+7
def main():
	ans =1
	n = int(input())
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print(0)
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()

Submission status: Accepted

Solution code:
mod = 10**9+7
def main():
	ans =1
	n = int(input())
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print(0)
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    R = 0
    G = 0
    B = 0
    ans = 1
    for a in A:
        if a == R == G == B:
            ans *= 3
            ans %= MOD
            R += 1
        else:
            if a == R == G:
                ans *= 2
                ans %= MOD
                R += 1
            elif a == G == B:
                ans *= 2
                ans %= MOD
                G += 1
            elif a == B == R:
                ans *= 2
                ans %= MOD
                B += 1
            else:
                if a == R:
                    R += 1
                elif a == G:
                    G += 1
                elif a == B:
                    B += 1
                else:
                    print(0)
                    sys.exit()
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def solve(n, a):
    dp = [3] + [0] * n
    res = 1
    for x in a:
        res = res * dp[x] % MOD
        if res == 0:
            break
        dp[x] -= 1
        dp[x+1] += 1
    return res

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

Submission status: Accepted

Solution code:
import sys

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

G={k:0 for k in range(-1,max(A)+1)}
G[-1]=3

X=1
for a in A:
    X*=G[a-1]-G[a]
    X%=M
    G[a]+=1
print(X)

Submission status: Accepted

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

ans=1
d={}
for i in range(N+1):
	d[i]=0

d[0]=3

for a in A:
	ans*=d[a]
	d[a]-=1
	d[a+1]+=1
	if ans>=10**9+7:
		ans=ans%(10**9+7)


print(ans)


# 2darray [[0] * 4 for i in range(3)]

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

t=[0,0,0]
ans=1

for i in range(n):
    now=A[i]
    cnt=0
    for q in range(3):
        if t[q]==now:
            cnt+=1
    ans=ans*cnt%mod
    for q in range(3):
        if t[q]==now:
            t[q]+=1
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
  d = defaultdict(lambda: 0)
  N = int(input())
  A = list(map(int, input().split()))
  mod = 10**9+7
  d[0] = 3
  ans = 1
  for i in range(N):
    if d[A[i]]==0:
      return 0
    ans *= d[A[i]]
    ans %= mod
    d[A[i]] -= 1
    d[A[i]+1] += 1
  return ans
print(solve())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
n = int(input())
nums = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(n + 1)]

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

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    cnt = [0] * 3
    ans = 1

    for x in a:
        p = cnt.count(x)
        if p == 0:
            return print(0)
        ans *= p
        ans %= MOD
        cnt[cnt.index(x)] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnts = [0,0,0]
sames = 0
ind = -1
res = 1
for a in a_list:
    for i, cnt in enumerate(cnts):
        if cnt == a: 
            sames += 1
            ind = i
    res *= sames
    res %= MOD
    cnts[ind] += 1
    sames = 0

print(res)

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    hat_cnt = [0, 0, 0]
    ans = 1
    for a in A:
        t = len([c for c in hat_cnt if c == a])
        if t == 0:
            ans = 0
            break
        ans *= t
        ans %= MOD
        for i in range(len(hat_cnt)):
            if hat_cnt[i] == a:
                hat_cnt[i] += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans =1
mod = 10**9+7
row = [0] *3
for i in range(N):
    
    ans *=row.count(A[i])
    ans %=mod
    for j in range(3):
        if row[j]==A[i]:
            row[j]+=1
            break
    

        
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
x, y, z = 0, 0, 0
ans = 1
for a in map(int, input().split()):
    if a == x:
        if x != y:
            x += 1
        elif y != z:
            ans = ans * 2 % MOD
            y += 1
        else:
            ans = ans * 3 % MOD
            z += 1
    elif a == y:
        if y != z:
            y += 1
        else:
            ans = ans * 2 % MOD
            z += 1
    elif a == z:
        z += 1
    else:
        ans = 0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7

def main():
    n = int(input())
    A = list(map(int, input().split()))
    candidates = [0] * (n+1)
    candidates[0] = 3
    ans = 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
ans = 1
r = 0
g = 0
b = 0

for x in a:
    ans = ans * ( (r == x) + (g == x) + (b == x) ) % (10**9+7)
    if r == x:
        r += 1
    elif g == x:
        g += 1
    else:
        b += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
ans=1
mod=1000000007
for i in range(n):
    aa=a[i]
    tmp=0
    flg=False
    for j in range(3):
        if aa==b[j]:
            tmp+=1
            if flg==False:
                b[j]+=1
                flg=True
    ans*=tmp
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi())
    MOD = 1000000007

    count=[0]*(N+1)
    zero = 0
    ans = 1
    for i in range(N):
        a = A[i]
        if a == 0:
            ans *= (3-zero) % MOD
            zero += 1
        else:
            b = a-1
            ans *= count[b] % MOD
            # print(count[b])
            count[b] -= 1
        
        count[a] += 1
        ans %= MOD

    ans %= MOD
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = int(1e9+7)

CNT = [0] * (N+10)
CNT[-1] = 3
ans = 1
for a in A:
  CNT[a] += 1
  ans *= CNT[a-1]
  ans %= mod
  CNT[a-1] -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    P = 10 ** 9 + 7
    num = [0, 0, 0]
    ans = 1
    for a in A:
        cnt = num.count(a)
        if cnt == 0:
            ans = 0
            break
        ans = (ans * cnt) % P
        num[num.index(a)] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in a:
  count=0
  flg=True
  for j in range(3):
    if rbg[j]==i:
      count+=1
      if flg:
        rbg[j]+=1
        flg=False
  ans*=count
  ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(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())
As = list(map(int, input().split()))
P = 1000000007

lst = [0,0,0]
rlt = 1

for i in range(N):
  cnt = lst.count(As[i])
  rlt *= cnt
  rlt %= P
  for j in range(3):
    if lst[j] == As[i]:
      lst[j] += 1
      break
      
print(rlt)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
ans = 1
M = 10**9+7
s = [0,0,0]
for i,num in enumerate(a):
    if num not in s:
        ans = 0
        break
    ans *= sum(item==num for item in s)
    ans %= M
    s[s.index(num)] += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
data = [0]*3
ans = 1
mod = pow(10,9)+7
for i in A:
    ans *= data.count(i)
    ans %= mod
    if ans == 0:
        break
    data[data.index(i)] += 1
print(ans)

Submission status: Accepted

Solution code:

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

L = 1000000007

state = [0,0,0]

M = [0,0,0]
for a in A:
    t = None
    n = 0
    for i,s in enumerate(state):
        if s == a:
            t = i
            n += 1
    if n == 0:
        break
    M[n-1] += 1
    state[t] += 1

if n > 0:
    x = 2**30 % L
    y = 3**19 % L


    k = M[1] % x
    l = M[2] % y
    r = 2**k * 3**l % L
    print(r)
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7
# N = 6
# A = [0, 1, 0, 0, 1, 2]

xyz = [[0]*(N+1) for _ in range(3)]
for i in range(N):
    is_added = False
    for j in range(3):
        if xyz[j][i] == A[i] and not is_added:
            xyz[j][i+1] = xyz[j][i] + 1
            is_added = True
        else:
            xyz[j][i+1] = xyz[j][i]

# for i in range(3):
#     print(xyz[i])

ans = 1
for i in range(N):
    cnt = 0
    for j in range(3):
        if xyz[j][i] == A[i]:
            cnt += 1
    ans = ans*cnt % MOD
print(ans)

Submission status: Accepted

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

ans = 1
MOD = 1000000007
cnt = [0 for _ in range(N+1)]
cnt[0] += 3

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:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
ans=1
for i in a:
  ans*=b.count(i)
  for j in range(3):
    if b[j]==i:
      b[j]+=1
      break
print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# E - Colorful Hats 2
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
count = [0]*N+[3]
used = [0]*(N+1)
ans = 1
for x in A:
    ans = (ans*(count[x-1]-used[x-1]))%MOD
    count[x] += 1
    used[x-1] += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
cnt = [0]*(n+1)
cnt[-1] = 3
mod = 1000000007
ans = 1
for i in range(n):
    ans *= cnt[a[i]-1]
    ans %= mod
    cnt[a[i]-1] -= 1
    cnt[a[i]] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

res = 1
for i,a in enumerate(A):
  res *= cnt[a]
  res %= MOD
  cnt[a] -= 1
  cnt[a+1] += 1

print(res % MOD)

Submission status: Accepted

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

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    if ans == 0:
        break
    cnt[cnt.index(A[i])] += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
ans = 1
MOD = 10**9+7
r, g, b = 0, 0, 0

for Ai in A:
    cnt = 0
    
    if r==Ai:
        cnt += 1
    
    if g==Ai:
        cnt += 1
    
    if b==Ai:
        cnt += 1
        
    ans *= cnt
    ans %= MOD
    
    if r==Ai:
        r += 1
    elif g==Ai:
        g += 1
    else:
        b += 1
    
print(ans)

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    MOD = 10**9 + 7
    MAX_N = 10**5

    count_arr = [0]*(MAX_N+1)
    count_arr[0] = 3

    ans = 1
    for a in A:
        ans *= count_arr[a]
        ans %= MOD

        count_arr[a] -= 1
        count_arr[a+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

RGB = [0, 0, 0]

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * 3
    ret = 1
    for i in range(N):
        ret *= C.count(A[i])
        ret %= mod
        for j in range(3):
            if C[j]==A[i]:
                C[j]+=1
                break
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,*A = map(int, open(0).read().split())
group = [0] * 3
ans = 1
for x in A:
    ans = (ans*group.count(x)) % 1000000007
    if ans == 0:
        print(0)
        break
    else:
        group[group.index(x)] += 1
else:
    print(ans)

Submission status: Accepted

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

ans=1
for i in range(N):
    cnt=0
    idx=-1
    for j in range(3):
        if A[i]==B[j]:
            cnt+=1
            idx=j
    ans=ans*cnt
    ans=ans%mod
    B[idx]+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
cnt = [0,0,0] # 現在割り当てられている人数
ans = 1 # 現時点での組み合わせ
for a in A:
    idx = []
    for i in range(3):
        if cnt[i] == a: # 割り当て可能
            idx.append(i)
    if len(idx)==0: # 割り当て不能
        print(0)
        exit()
    cnt[idx[0]]+=1 # 任意の色で良いので、一番番号が若い色とする
    ans *= len(idx) # 割り当て可能な人数をかける
    ans %= MOD
print (ans)

Submission status: Accepted

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

mod = 1000000007

cnt = [0] * 3
ans = 1

for i in range(n):
    count = 0
    minj = 4
    for j in range(3):
        if hats[i] == cnt[j]:
            count += 1
            minj = min(minj, j)
    if count == 0:
        ans = 0
        break
    cnt[minj] += 1

    ans = ans * count % mod

print(ans)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n=II()
	A=LI()
	B=[0]*(n+1)
	ans=1
	B[0]=3

	for i in range(n):
		ans*=(B[A[i]])-(B[A[i]+1])
		ans%=10**9+7
		B[A[i]+1]+=1

	print(ans)








if __name__ == "__main__":
	main()

Submission status: Accepted

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

ans=1

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

print(ans%mod)

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))
res=1
cnt=[0]*3
for i in range(N):
    res=res*cnt.count(A[i])%MOD
    for j in range(3):
        if cnt[j]==A[i]:
            cnt[j]+=1
            break
print(res)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def era(n):
    ret = [1 for i in range(n + 2)]
    for i in range(2, int(math.sqrt(n) +3)):
        if ret[i] != 0:
            for j in range(2, n//i + 1):
                ret[i * j] = 0
    rret = []
    for i, r in enumerate(ret):
        if r == 1 and i != 0:
            rret.append(i)

    return rret


def houjyo(n, m, k, kaijyo):
    # kaburi ... k
    # all ... n
    if k == n:
        return 1
    else:
        # kasanarierabi nck * nokorierabi (m - k)p(n-k) - houjyo(+1)
        ret = nck(n,k,kaijyo) * npk(m-k, n-k, kaijyo) # - (k + 1) * houjyo(n, m, k+1, kaijyo)
        # print(nck(n,k,kaijyo) , npk(m-k, n-k, kaijyo))
        return ret % MOD


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n = getN()
    nums = getList()

    ref = [0,0,0]
    ans = 1
    for num in nums:
        tmp = num
        ref.sort()
        if ref[0] == tmp:
            if ref[0] == ref[1]:
                if ref[0] == ref[2]:
                    ans *= 3
                else:
                    ans *= 2
            ref[0] += 1

        elif ref[1] == tmp:
            if ref[1] == ref[2]:
                ans *= 2

            ref[1] += 1
        elif ref[2] == tmp:
            ref[2] += 1
        else:
            print(0)
            return
        ans %= MOD
        # print(ans)

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


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

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
B = [3 if i == 0 else 0 for i in range(N + 1)]
MOD = 1000000007
ans = 1
for a in A:
    ans = ans * B[a] % MOD
    if ans == 0:
        break
    else:
        B[a] -= 1
        B[a + 1] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    mod = 10**9 + 7
    num = [0] * 3
    ans = 1

    for i in range(N):
        min_j = 4
        count = 0
        for j in range(3):
            if num[j] == A[i]:
                count += 1
                min_j = min(min_j, j)
        if min_j == 4:
            ans = 0
            break
        num[min_j] += 1
        ans *= count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

ans = 1
cnt = [0, 0, 0]
for i in range(N):
	ans = ans * cnt.count(A[i]) % mod
	if A[i] in cnt:
		cnt[cnt.index(A[i])] += 1
	else:
		print(0)
		exit()

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_dic = {}
for i in range(n):
  a_dic[i] = 3

ans = 1
for a in a_list:
  if a == 0:
    ans = ans * a_dic[a]
    a_dic[a] -= 1
  else:
    ans = ans * (a_dic[a] - a_dic[a-1])
    a_dic[a] -= 1
    
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = 1000000007
d = [0,0,0]
ans = 1
for i in range(n):
    if d[0] == d[1] == d[2] == a[i]:
        ans *= 3
        d[0] += 1
    elif (d[0] == d[1] or d[1] == d[2]) and a[i] == d[1]:
        ans *= 2
        d[1] += 1
    elif a[i] == d[0]:
        d[0] += 1
    elif a[i] == d[1]:
        d[1] += 1
    elif a[i] == d[2]:
        d[2] += 1
    
    else:
        ans = 0
        break
      
    ans %= m
    d = sorted(d,reverse=True)
print(ans)

Submission status: Accepted

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

status = [0, 0, 0]
mod = 1000000007

ans = status.count(a[0])
status[0] += 1

for i in range(1, n):
    ans *= status.count(a[i])
    ans %= mod

    for j in range(len(status)):
        if status[j] == a[i]:
            status[j] += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = [0,0,0]
Ans = 1
MOD = 1000000007
for a in A:
    ask = C.count(a)
    if ask==0:
        Ans=0
        break
    ind = C.index(a)
    C[ind] += 1
    Ans = (Ans*ask)%MOD
print(Ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    ans = 1
    cnt = [0] * (N + 1)
    for i in range(N):
        if A[i] == 0:
            ans *= 3 - cnt[A[i]]
            cnt[A[i]] += 1
        else:
            ans *= cnt[A[i]-1] - cnt[A[i]]
            cnt[A[i]] += 1
        ans %= MOD

    print(ans)

    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e

import sys
input=sys.stdin.readline
MOD=10**9+7

def main():
    N=int(input())
    A=list(map(int,input().split()))
    cnt=[0]*N
    ans=1
    for i in range(N):
        if A[i]==0:
            ans*=3-cnt[0]
            ans%=MOD
            cnt[A[i]]+=1
        else:
            ans*=cnt[A[i]-1]-cnt[A[i]]
            ans%=MOD
            cnt[A[i]]+=1
    print(ans)
        
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0,0,0]
count = 1
for i in range(n):
    match = (a[i]==c[0])+(a[i]==c[1])+(a[i]==c[2])
    if match==0:
        count = 0
        break
    elif match==1 or a[i]==0:
        c[c.index(a[i])] += 1
    else:
        c[c.index(a[i])] += 1
        count = (count*match)%(1e+9+7)
               
if count != 0:
    c = sorted(c,reverse=True)
    while 0 in c:
        c.pop()
    memory = set()
    kinds = 0
    for x in c:
        if not x in memory:
            kinds += 1
    for i in range(3,3-kinds,-1):
        count = (count*i)%(1e+9+7)

print(int(count))