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

huts=[0, 0, 0]
out=1
for i in range(N):
  out*=huts.count(A[i])
  if out==0:
    print(0)
    exit()
  huts[huts.index(A[i])]+=1
print(out%MOD)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    r = 1
    c = collections.defaultdict(int)
    c[0] = 3
    for b in a:
        r *= c[b]
        r %= mod
        c[b] -= 1
        c[b+1] += 1

    return r


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    RGB = [-1, -1, -1]
    ans = 1
    for a in A:
        count = 0
        for i in range(3):
            if RGB[i] == a-1:
                if count == 0:
                    RGB[i] = a
                count += 1
        if count > 1:
            ans *= count
            ans %= MOD
        elif count == 0:
            ans = 0
            print(ans)
            return
    print(ans)

    return


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:
n = int(input())
lis = list(map(int,input().split()))
num = [0 for i in range(n)]
ans = 1
for nu in lis:
    if nu == 0:
        ans *= (3-num[0])
    else:
        ans *= (num[nu-1]-num[nu])
    ans %= 10 ** 9 + 7
    num[nu] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

# numpy and scipy are available for use
import numpy
import scipy
#https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
#Colorful Hats 2
"""
"""

# reads a single line
N = gi()
tails = [0] * (N + 5)

tails[0] = 3
ans = 1
for i in range(N):
    a = gi()
    ans *= tails[a]
    ans %= MOD
    tails[a] -= 1
    tails[a + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

A=list(map(int,input().split()))
l=[3]+[0]*(10**6)

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

Submission status: Accepted

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

inf = 10**9+7
occ = [0]*(N+1)
#便宜上-1がすでに3回出ていることにする&ナンバリングをずらす
occ[0]=3

ans = 1

for i in range(0,N):
    ans=ans*(occ[A[i]]-occ[A[i]+1])%inf
    occ[A[i]+1]+=1

print(ans)

Submission status: Accepted

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

c=1
for a in A:
    c*=B[a]
    c%=1000000007
    B[a]-=1
    B[a+1]+=1

print(c)

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]
MOD = 10**9+7

N = INT()
A = MAP()

B = [0] * N
C = [0, 0, 0]
for i, a in enumerate(A):
	flg = False
	for j, c in enumerate(C):
		#print(a, c)
		if a==c:
			B[i] += 1
			if not flg:
				C[j] += 1
				flg += 1

#print(B)
#print(C)

ans = 1
for b in B:
	ans *= b
	ans %= MOD

print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(int)
    d[-1] = 3
    cnt = 1
    for v in a:
        cnt *= d[v-1]
        d[v] += 1
        d[v-1] -= 1
        cnt %= mod
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
cnt = [0]*N
p = 0
ans = 1
MOD = 10**9+7

for Ai in A:
    if Ai==0:
        cnt[Ai] += 1
        p += 1
    else:
        ans *= cnt[Ai-1]
        ans %= MOD
        cnt[Ai-1] -= 1
        cnt[Ai] += 1

if p==1:
    ans *= 3
elif p==2:
    ans *= 6
elif p==3:
    ans *= 6
else:
    ans = 0

print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

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


print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
X=[-1,-1,-1]
ans=1
mod=10**9+7
for i in range(N):
    tmp=0
    if A[i]>i:
        ans=0
    for j in range(3):
        if X[j]==A[i]-1:
            tmp+=1
    for j in range(3):
        if X[j]==A[i]-1 or tmp==0:
            ans=tmp*ans
            ans%=mod
            X[j]+=1
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
c1, c2, c3 = -1, -1, -1
ptn = 0
ptn_sum = 1

for i in range(n):
  if a[i] == c1+1:
    ptn += 1
  if a[i] == c2+1:
    ptn += 1
  if a[i] == c3+1:
    ptn +=1
    
  if a[i] == c1+1:
    c1 += 1
  elif a[i] == c2+1:
    c2 += 1
  elif a[i] == c3+1:
    c3 += 1  
  ptn_sum *= ptn
  ptn =0
print(ptn_sum%1000000007)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
c = [0]*3
ans = 1
for x in a:
  t = c.count(x)
  ans = ans*t%mod
  if not t:
    break
  c[c.index(x)] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()


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



print(ans)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    N = int(f_i.readline())
    A = tuple(map(int, f_i.readline().split()))
    
    ans = 1
    xyz = [0, 0, 0]
    for A_i in A:
        cnt = xyz.count(A_i)
        if cnt == 0:
            print(0)
            break
        ans *= cnt
        ans %= mod
        xyz[xyz.index(A_i)] += 1
    else:
        print(ans)

solve()

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
    b.append([b[-1][j]+1 if j==k else b[-1][j] for j in range(3)])
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())
alist=[int(i) for i in input().split()]

zeros=0
answer=1
triple=[0,0,0]

for i in range(n):
    now=alist[i]
    if now==triple[0]:
        if now==triple[1]:
            if now==triple[2]:
                answer*=3
            else:
                answer*=2
        triple[0]+=1
    else:
        if now==triple[1]:
            if now==triple[2]:
                answer*=2
            triple[1]+=1
        else:
            if now==triple[2]:
                triple[2]+=1
            else:
                answer=0
    answer%=(1000000007)

print(answer)

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(int,input().split()))
x,y,z = [0]*(n+1),[0]*(n+1),[0]*(n+1)
tmp = [0]*n
for i,a in enumerate(aa):
  tmp[a]+=1
  if tmp[a]==1:
    x[i+1] = x[i]+1
    y[i+1] = y[i]
    z[i+1] = z[i]
  elif tmp[a]==2:
    x[i+1] = x[i]
    y[i+1] = y[i]+1
    z[i+1] = z[i]
  else:
    x[i+1] = x[i]
    y[i+1] = y[i]
    z[i+1] = z[i]+1
ans=1
for a,b,c,d in zip(x[:n],y[:n],z[:n],aa):
  ans = ans*[a,b,c].count(d)
print(ans%(10**9+7))

Submission status: Accepted

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

ptn = [3] + [0] * (max(a) + 1)
ans = 1
for i in a:
    ans *= ptn[i]
    ptn[i] -= 1
    ptn[i + 1] += 1

print(ans % 1000000007)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

N = I()
A = III()

d = defaultdict(list)
for i in range(N):
    d[A[i]].append(i)

ans = 1
val = 3
for i in range(max(d.keys())+1):
    if len(d[i])>val:
        print(0)
        exit()
    else:
        if i==0:
            before = d[i]
            val = len(d[i])
        else:
            x = []
            for k in d[i]:
                x.append(sum([k>b for b in before]))
            z = 1
            for j,x1 in enumerate(x):
                z *= max(x1-j,0)
            if z==0:
                print(0)
                exit()
            else:
                ans *= z
                ans %= mod
            before = d[i]
m = 0
for x in d.values():
    if len(x)>=m:
        m = len(x)
if m==1:
    ans *= 3
    ans %= mod
else:
    ans *= 6
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
dp = [0,0,0]
ans = 1
mod = 1000000007

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

Submission status: Accepted

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

Submission status: Accepted

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

mod=1000000007
hat=[0]*3
ans=1
for a in A:
  c=hat.count(a)
  if c==0:
    print(0)
    exit()
  ans=(ans*c)%mod
  i=hat.index(a)
  hat[i]+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
row = list(map(int, input().split()))
count = [3]+([0]*n)
ans = 1

for i in row:
    ans *= count[i]
    count[i] -= 1
    count[i+1] += 1

print(ans%1000000007)

Submission status: Accepted

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

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

mod = 1000000007

ans = 1

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


print(ans)

Submission status: Accepted

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

x[0]=3
ans=1

for i in range(n):
    if a[i]==0 and x[0]>0:
        ans*=x[0]
        ans%=mod
        x[0]-=1
        x[1]+=1
    
    elif a[i]==0 and x[0]==0:
        print(0)
        exit()
    
    else:
        if x[a[i]]>0:
            ans*=x[a[i]]
            ans%=mod
            x[a[i]]-=1
            x[a[i]+1]+=1
        
        else:
            print(0)
            exit()
        

print(ans)

Submission status: Accepted

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = inputIntList()

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

    ret = 1
    for a in A:
        ret *= pattern[a]
        pattern[a] -= 1
        pattern[a + 1] += 1
        # print(pattern)
    return ret % 1000000007


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

Submission status: Accepted

Solution code:
M=1000000007

N = int(input())
A = [-1] + list(map(int,input().split()))

x = [0]*(N+1)
y = [0]*(N+1)
z = [0]*(N+1)
ans=1

for i in range(1,N+1):
    if A[i] == x[i-1] and A[i] == y[i-1] and A[i] == z[i-1]:
        ans = (ans * 3) %M
    elif A[i] == x[i-1] and A[i] == y[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == y[i-1] and A[i] == z[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == z[i-1] and A[i] == x[i-1]: 
        ans = (ans * 2) %M
    if A[i] == x[i-1]:
        x[i]=x[i-1]+1
        y[i]=y[i-1]
        z[i]=z[i-1]
    elif A[i] == y[i-1]:
        x[i]=x[i-1]
        y[i]=y[i-1]+1
        z[i]=z[i-1]
    elif A[i] == z[i-1]:
        x[i]=x[i-1]
        y[i]=y[i-1]
        z[i]=z[i-1]+1
    else:
        ans = 0
        break

print(ans)

Submission status: Accepted

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

MOD = 1000000007

def f(A):
    Q = [0]*3
    X = 1
    
    for a in A:
        Q2 = list(filter(lambda iq: iq[1] == a, enumerate(Q)))

        if len(Q2) == 0:
            return 0
        
        X *= len(Q2)
        X %= MOD
        

        Q[Q2[0][0]] += 1

    return X



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

    print(f(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#三井住友信託銀行プログラミングコンテスト2019 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Submission status: Accepted

Solution code:
def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def next_state(c, a, n_patterns):
    # c := c[0] >= c[1] >= c[2]
    idx = -1
    for i in range(3):
        if c[i] == a:
            idx = i
            break
    if idx == -1:
        return -1, -1
    n_equals = 1
    n_equals += 1 if c[idx%3] == c[(idx + 1) % 3] else 0
    n_equals += 1 if c[idx%3] == c[(idx + 2) % 3] else 0
    c[idx%3] += 1
    n_patterns *= n_equals
    n_patterns %= 1000000007
    return c, n_patterns

def solve(N, A):
    c = [0, 0, 0]
    n = 1
    for a in A:
        c, n = next_state(c, a, n)
        if c == -1 and n == -1:
            return 0
    return n
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3 or len(li[0])==0:
		print(0)
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6
	for i in range(1,aa+1):
		if len(li[i])>3 or len(li[i])==0 or len(li[i])>len(li[i-1]):
			print(0)
			exit(0)
		else:
			k=bisect.bisect_right(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_right(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Accepted

Solution code:
N = int(input())
lst = [int(i) for i in input().split()]
mod = 1000000007
count = [0] * (N + 1)
count[0] = 3

ret = 1
for i in lst:
    count[i + 1] += 1
    ret = (ret * count[i]) % mod
    count[i] -= 1

print(ret)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (max(A) + 1)
ans = 1
for a in A:
    if a > 0:
        ans *= counts[a - 1]
        ans %= MOD
        counts[a - 1] -= 1
    counts[a] += 1
c0 = A.count(0)
if c0 == 1:
    print(ans * 3 % MOD)
elif c0 in (2, 3):
    print(ans * 6 % MOD)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))
 
ans = 1
r,g,b = 0,0,0
 
for x in a:
    ans *= [r,g,b].count(x)

    if r == x:r+=1
    elif g == x:g +=1
    elif b == x:b +=1
    else:
        print(0)
        sys.exit()
ans %= 1000000007 
print(ans)

Submission status: Accepted

Solution code:
mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    # ele in cur can choose ele in last which is smaller than it
    # person says i can choose person says i-1 who is in front of him
    # cur and last are naturally increase order
    ans = 1
    minus = 0
    for i in cur:
        count = 0
        for j in last:
            if j < i:
                count += 1
        ans *= count-minus
        minus += 1
    return ans
    # j = 0
    # ans = 1
    # for i in range(len(cur)):
    #     while j < len(last):
    #         if last[j] < cur[i]:
    #             j += 1
    #         else:
    #             break
    #     ans *= (j-i)
    # return ans

memo.append([-1,-1,-1]) # for convenience
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    # if len(memo[i]) == 1:
    #     break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

cnt = defaultdict(int)
cnt[-1] = 3
ans = 1
for i in range(n):
    ans *= max(cnt[a[i] - 1] - cnt[a[i]], 0)
    ans %= MOD

    cnt[a[i]] += 1

print(ans)

Submission status: Accepted

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

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

for x in a:
    ans *= [r, g, b].count(x)

    if r == x:r += 1
    elif g == x:g += 1
    elif b == x:b += 1

    else:
        print(0)
        exit()

ans %= 1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  from collections import defaultdict
  N = int(input())
  A = list(map(int,input().split()))
  MOD = 1000000007
  c = defaultdict(int)
  c[0] = 3
  ans = 1
  for i in range(N):
    if not c[A[i]]:
      print(0)
      exit()
    ans *= c[A[i]]
    ans %= MOD
    c[A[i]] -= 1
    c[A[i]+1] += 1
  print(ans)
main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
x=0
y=0
z=0
ans=1
for a in A:
    c=0
    X,Y,Z=x,y,z
    if a==x:
        x+=1
        c+=1
    if a==y:
        c+=1
        if a!=X:
            y+=1
    if a==z:
        c+=1
        if a!=X and a!=Y:
            z+=1
    ans=ans*c%1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

ans = 1
count = 0
lst = [0] * (N + 1)
for a in A:
    if a == 0:
        ans *= (3 - count)
        count += 1
        lst[a] += 1
    else:
        ans *= lst[a - 1]
        lst[a] += 1
        lst[a - 1] -= 1
    ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
xyz,T = [0,0,0],1
for Ai in A:
  n_Ai = xyz.count(Ai)
  T = (T*n_Ai)%1000000007
  if n_Ai>0: xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Accepted

Solution code:
mod = 1000000007

def mul(x, y):
    return x * y % mod

def f(n, arr):
    answer = 1
    count = [0 for _ in range(n + 1)]
    count[0] = 3
    for e in range(n):
        answer = mul(answer, count[arr[e] - 1] - count[arr[e]])
        count[arr[e]] = count[arr[e]] + 1
        # print("answer ", answer)
    return answer

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split(' ')))
    for i in range(n):
        arr[i] = arr[i] + 1 
    print(f(n, arr))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = 1
l = [0] * n
for k in range(n):
    xl = l[a[k]]
    if a[k] == 0:
        xs = 3
    else:
        xs = l[a[k] - 1]
    if xs + 1 != xl:
        x = x * (xs - xl) % 1000000007
    l[a[k]] = l[a[k]] + 1
print(x)

Submission status: Accepted

Solution code:
import sys
bbn=1000000007

#+++++



		
def main():
	n = int(input())
	aal = list(map(int, input().split()))
	cc=[0,0,0]
	total_count=1
	for nh in aal:
		nc = cc.count(nh)
		total_count = (total_count * nc ) % bbn
		if total_count == 0:
			return 0
		
		ii=cc.index(nh)
		#pa((cc, total_count,ii,nh,nc))
		cc[ii]+=1
		
	print(total_count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
mod = 10**9+7

ans = 1
n = [0,0,0]
for i in A:
    cnt = 0
    for ind ,j in enumerate(n):
        if i == j:
            cnt += 1
    for ind ,j in enumerate(n):
        if i == j:
            n[ind] += 1
            break
    ans = ans*cnt
    ans = ans % mod
print(ans)

Submission status: Accepted

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

mod = int(1e+9 + 7)
L = [0, 0, 0]
pi = 1
for i in range(N):
  j = 0
  while L[j] != A[i]:
    j += 1
    if j == 3:
      break
  n = 0
  for k in range(3):
    if L[k] == A[i]:
      n += 1
  if j != 3:
    L[j] += 1
  pi *= n
  pi %= mod
print(pi)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

N, *A = map(int, read().split())
mod = 10 ** 9 + 7

hats = [0] * 3
answer = 1

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

print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

N, *A = map(int, read().split())
mod = 10 ** 9 + 7

hats = [[0] * 3 for _ in range(N + 1)]
answer = 1

for i in range(N):
    answer *= hats[i].count(A[i])
    answer %= mod
    flag = True
    for j in range(3):
        if hats[i][j] == A[i] and flag:
            hats[i + 1][j] = A[i] + 1
            flag = False
        else:
            hats[i + 1][j] = hats[i][j]

print(answer)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

vec = [0, 0, 0]
num = 1

for a in A:
    idx = [i for i, x in enumerate(vec) if x == a]
    if len(idx) == 0:
        print(0)
        exit()
    num = (num * len(idx)) % MOD
    vec[idx[0]] += 1

print(num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

ans = 1
numRGBs = [0] * 3
for A in As:
    num = 0
    for i in range(3):
        if numRGBs[i] == A:
            num += 1
            if num == 1:
                numRGBs[i] += 1
    ans *= num
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

mod = 10**9 + 7

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

c = Counter()
c[-1] = 3
ans = 1
for i in range(N):
    ans *= c[A[i]-1] - c[A[i]]
    c[A[i]] += 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[0]*(n+1)
c[0]=3
cnt=1
for i in a:
  cnt=cnt*c[i]%1000000007
  c[i]-=1
  c[i+1]+=1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import combinations
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
a = [int(item) for item in input().split()]

rgb = [-1, -1, -1]
ans = 1
for item in a:
    cnt = rgb.count(item - 1)
    if cnt == 0:
        print(0)
        exit()
    rgb[rgb.index(item-1)] = item
    ans *= cnt
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
H = [0] * 3
P = 1
for i in A:
	if H.count(i) == 0:
		P = 0
		break
	P *= H.count(i)
	P %= 1000000007
	H[H.index(i)] += 1
print(P)

Submission status: Accepted

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

for a in A:
  ans = ans * cnt[a] % MOD
  if ans == 0:
    break
  cnt[a] -= 1 #分布状態の変化
  cnt[a+1] += 1
  
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n , *a_s = map(int,open(0).read().split())
tmp = [3] + [0 for _ in range(n+1)]
ans = 1
for a in a_s:
  ans = ans * tmp[a] % 1000000007
  tmp[a] -= 1
  tmp[a+1] += 1
  
print(ans)