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
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

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

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

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

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def solve(N, A):
    ret = ModInt(1)
    count = [3 if not i else 0 for i in range(N + 1)]

    for a in A:
        ret *= count[a]
        if not ret:
            break
        count[a] -= 1
        count[a + 1] += 1

    return ret

if __name__ == "__main__":
    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()))

#n=54
#a=[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]
#ans=115295190

#n=10
#a=[3,2,5,1,7,3,6,4,5,4]
#ans=0

if a[0]!=0:
    print(0)
    sys.exit()
 
mod=10**9+7
acnt=dict()
acnt[a[0]]=1
acntkeymax=0
t=3
for i in range(1,n):

    if a[i] in acnt:
        acnt[a[i]]+=1
        if acnt[a[i]]>3:
            print(0)
            sys.exit()
    else:
        if acntkeymax+1==a[i]:
            acntkeymax=a[i]
            acnt[a[i]]=1
        else:
            print(0)
            sys.exit()

    if a[i]!=0:
        if acnt[a[i]-1]==1:
            if acnt[a[i]]!=1:
                print(0)
                sys.exit()
        elif acnt[a[i]-1]==2:
            if acnt[a[i]]==1:
                t=(t*2)%mod
            elif acnt[a[i]]!=2:
                print(0)
                sys.exit()
        elif acnt[a[i]-1]==3:
            if acnt[a[i]]==1:
                t=(t*3)%mod
            elif acnt[a[i]]==2:
                t=(t*2)%mod
            elif acnt[a[i]]!=3:
                print(0)
                sys.exit()
    else:
        if acnt[0]==2:
            t=(t*2)%mod
        elif acnt[0]!=3:
            print(0)
            sys.exit()

#    print("i:",i,"a[i]:",a[i],"acnt[a[i]]:",acnt[a[i]],"t:",t)
                
print(t)

Submission status: Accepted

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

mod = 10**9 + 7

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

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    cunt=[0]*(n+1)
    cunt[0]=3
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*cunt[a]%mod
        if ans==0:break
        cunt[a+1]+=1
        cunt[a]-=1
    print(ans)
    

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    rgb=[-1,-1,-1]
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*Counter(rgb)[a-1]%mod
        if ans==0:break
        rgb[rgb.index(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
if A[0]!=0:
    print(0)
    exit()
L=[1,0,0]
ans=3
for i in range(1,N):
    a=A[i]
    count=0
    add=True
    for j,l in enumerate(L):
        if a==l:
            count+=1
            if add:
                L[j]+=1
                add=False

    ans*=count
    ans%=mod
print(ans)
#print(L)

Submission status: Accepted

Solution code:
#三井住友信託銀行プログラミングコンテスト2019 -E Colorful Hats 2
"""
適当に色を割り振って良い。
[0,0,0]の状態から、その数字がいくつあるかを掛けていく
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = list(map(int,readline().split()))
mod = 10**9+7

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

Submission status: Accepted

Solution code:

def resolve():
    MOD = 1000000007
    N = int(input())
    A = list(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = na()

x = 0
y = 0
z = 0

def count(m):
    cnt = 0
    cnt += x == m
    cnt += y == m
    cnt += z == m
    return cnt

ans = 1
for i in range(n):
    ans *= count(a[i])
    if x == a[i]:
        x += 1
    elif y == a[i]:
        y += 1
    elif z == a[i]:
        z += 1

print(ans % mod)

Submission status: Accepted

Solution code:



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

if A[0] != 0:
    print(0)
    exit()


ans = 1
colors = [0] * 3
for n in A:
    ans *= colors.count(n)
    ans %= MOD
    for i in range(3):
        if colors[i] == n:
            colors[i] += 1
            break
print(ans)

Submission status: Accepted

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

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

ans = 1
for i in range(1, N+1):
    plus_flg = True
    tmp = 0
    for j in range(3):
        xyz[i][j] = xyz[i-1][j]
        if xyz[i-1][j] == A[i-1]:
            tmp += 1
            if plus_flg:
                xyz[i][j] = xyz[i-1][j] + 1
                plus_flg = False
    ans *= tmp
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())

res = 1
l = [0]*(n+1)
l[0] = 3
for a in list(map(int, input().split())):
    if l[a]<l[a+1]:
        print(0)
        exit()
    res = (res*(l[a] - l[a+1]))%mod
    l[a+1] += 1
print(res)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  dp=[0,0,0] # dp[j]:前から順番に見た時の帽子jの数
  ans=1
  for ai in a:
    if ai in dp:
      ans*=dp.count(ai)
      ans%=mod
      dp[dp.index(ai)]+=1
    else:
      print(0)
      exit()
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 1
cnt = [0] * N
for i, a in enumerate(A):
    cnt[a] += 1
    if a == 0:
        ans *= 4 - cnt[a]
    else:
        ans *= max(0, cnt[a-1]-cnt[a]+1)
    ans %= MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9+7

def main():
    N,*A = map(int, read().split())

    cnt = [0] * N
    ans = 1
    for a in A:
        if a == 0:
            cnt[0] += 1
            continue
        ans *= cnt[a - 1] - cnt[a]
        ans %= MOD
        cnt[a] += 1
        
    if cnt[0] == 1:
        ans *= 3
    elif cnt[0] <= 3:
        ans *= 6
    else:
        ans = 0
    
    ans %= MOD

    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
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  try:
    num_color[num_color.index(a-1)] = a
  except:
    print(0)
    quit()

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    # color_number[i][j]: [0, i)でj番目に多い色の人数
    color_number = [[0, 0, 0] for _ in range(N)]
    for i in range(N-1):
        if A[i] in color_number[i]:
            idx = color_number[i].index(A[i])
        else:
            idx = -1
        for j in range(3):
            if j==idx:
                color_number[i+1][j] = color_number[i][j] + 1
            else:
                color_number[i+1][j] = color_number[i][j]

    ans = 1
    for i in range(N):
        ans *= color_number[i].count(A[i])
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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
from fractions import gcd
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

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:
if __name__ == '__main__':
    n = int(input())
    a = list(map(lambda x: int(x) + 1, input().split()))
    counts = [0] * (n + 1)
    counts[0] = 3
    ans = 1
    for i in range(n):
        ans *= counts[a[i] - 1]
        ans %= (10 ** 9 + 7)
        counts[a[i] - 1] -= 1
        counts[a[i]] += 1
    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    x, y, z = [0], [0], [0]
    for i in range(n):
        if a[i] == 0:
            if x[-1] == 0:
                x.append(1)
                y.append(y[-1])
                z.append(z[-1])
            elif y[-1] == 0:
                x.append(x[-1])
                y.append(1)
                z.append(z[-1])
            else:
                x.append(x[-1])
                y.append(y[-1])
                z.append(1)
        else:
            if x[-1] == a[i]:
                x.append(x[-1] + 1)
                y.append(y[-1])
                z.append(z[-1])
            elif y[-1] == a[i]:
                x.append(x[-1])
                y.append(y[-1] + 1)
                z.append(z[-1])
            else:
                x.append(x[-1])
                y.append(y[-1])
                z.append(z[-1] + 1)

    ans = 1
    for i in range(n):
        ans *= [x[i], y[i], z[i]].count(a[i])
        ans %= (10 ** 9 + 7)

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

p =10**9+7

cnt= [0]*n
cnt[0]=1
ans = 3

if a[0]!=0:
    print(0)
    exit()

for i in range(1,n):
    if a[i]==0:
        ans *= (3-cnt[a[i]])
    else:
        ans *= (cnt[a[i]-1] - cnt[a[i]])
        if cnt[a[i]-1]==0:
            print(0)
            exit()

    ans%=p
    cnt[a[i]] += 1
    if cnt[a[i]]>3:
        print(0)
        exit()

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 1
    mod = 10 ** 9 + 7
    for i in range(n):
        A[i] += 1

    cnt = [0] * (n + 1)  # cnt[i]は、Aのなかでこれまでに何個iが登場したか。つまりiの候補数。
    cnt[0] = 3

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


resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
_, a = open(0)
mod = 10**9+7
c = 1
l = [3] + [0]*10**6

for a in a.split():
  a = int(a)
  c = c * l[a] % mod
  l[a] -= 1
  l[a+1] += 1
print(c)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    MOD = 1000000007

    res = 1
    cnt = {'R': 0, 'G': 0, 'B': 0}
    for a in A:
        cv = 0
        cc = 'R'
        for c, v in cnt.items():
            if v == a:
                cv += 1
                cc = c
        res *= cv
        res %= MOD
        cnt[cc] += 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
ans = 1
mod = 10 ** 9 + 7
memo = [0, 0, 0]
for check in a:
    if check in memo:
        ans *= memo.count(check)
        ans %= mod
        memo[memo.index(check)] += 1
    else:
        print(0)
        exit()
print(ans)

Submission status: Accepted

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

colors = [0]*3
ans = 1
for i in range(n):
    c = colors.count(A[i])
    ans = ans*c % MOD
    if c == 0:
        break
    colors[colors.index(A[i])] += 1

print(ans % MOD)

Submission status: Accepted

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

colors = [0]*3
dp = [0]*n
for i in range(n):
    c = colors.count(A[i])
    dp[i] = c
    if c == 0:
        break
    colors[colors.index(A[i])] += 1

ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    RGB = [1, 0, 0]
    ans = 1
    if A[0] !=0:
        print(0)
        return
    for i in range(1, N):
        a = A[i]
        if a == 0:
            if 0 in RGB:
                j = RGB.index(a)
                RGB[j] += 1
            else:
                print(0)
                return
        elif a not in RGB:
            print(0)
            return
        else:
            k = RGB.count(a)
            ans *= k
            ans %= MOD
            j = RGB.index(a)
            RGB[j] += 1
    z = RGB.count(0)
    if z == 0:
        ans *= 6
        ans %= MOD
    elif z == 1:
        ans *= 6
        ans %= MOD
    else:
        ans *= 3
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        if a not in cnt:
            print(0)
            return
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

xyz = [[0,0,0]for _ in range(n)]
xyz[0] = [0,0,0]

mod = 10**9+7

for i in range(n-1):
    if li[i] not in xyz[i]:
        print(0)
        exit()
    ix = xyz[i].index(li[i])
    for j in range(3):
        if j == ix:
            xyz[i+1][j] = xyz[i][j] + 1
        else:
            xyz[i+1][j] = xyz[i][j]

point = 3

for i in range(1,n):
    point *= xyz[i].count(li[i])
    point %= mod
print(point)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().strip().split(" ")))
dp = {i: dict() for i in range(N)}
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (ma, mi) in dp[i]:
        return dp[i][(ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[i][(ma, mi)] = 0
        return 0

    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[i][(ma, mi)] = ans % mod
    return ans % mod

print(f(0, 0, 0) % mod)

Submission status: Accepted

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


def solve():
    res = 1
    h = [0, 0, 0]
    for i in range(N):
        k = h.count(left[i])
        res = res * k % M
        for j in range(3):
            if h[j] == left[i]:
                h[j] += 1
                break
    return res


print(solve())

Submission status: Accepted

Solution code:
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Submission status: Accepted

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

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7
ctr = [0] * 3
ans = 1
for a in A:
    ans *= sum(a == v for v in ctr)
    for j in range(3):
        if ctr[j] == a:
            ctr[j] += 1
            break

print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

ka = [[0]*3 for _ in range(n+1)]

for i in range(n):
    for j in range(3):
        ka[i+1][j] = ka[i][j]
        
    for j in range(3):
        if ka[i][j] == a[i]:
            ka[i+1][j] += 1
            break
    ka[i+1].sort(reverse = True)
    
ans = 1
for i in range(n):
    mlt = 0
    for j in range(3):
        if ka[i][j] == a[i]:
            mlt += 1
            
    ans = ans * mlt % MOD
        
print(ans)

Submission status: Accepted

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

DIV = 10**9 + 7

# 0 1 2 3 4 5
# 最初の0で選べるのは3色
# その時点で青・赤・黄とも選択可能だから。

# 0 0 0 
# A (Aとは異なるので)B (A,Bとは異なるので)C
# A,B,Cに3色割り振るので 3 * 2 * 1 = 6

# そこまでにA,B,Cがいくつ出てきたかを記録する。
# 次に選べるもの（複数あればどれでもいい）を選定する
# そのときの候補の数を場合の数に掛け算

ABC = [0] * 3 # A,B,Cが順にいくつ使われたのかの管理

ans = 1
for i in range(N):
  num = A[i]
  first = True
  cnt = 0
  for j in range(len(ABC)):
    if ABC[j] == num:
      cnt += 1
      if first:
        ABC[j] += 1
        first = False
  ans = ((ans % DIV) * cnt)%DIV
  
print(ans)

Submission status: Accepted

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

print(ans%mod)

Submission status: Accepted

Solution code:
N=int(input())
A= list(map(int,input().split()))
B=[0,0,0]
C=1
for i in range(N):
 E=0
 F=0
 for j in range(3):
  if A[i]==B[j]:
   E+=1
   if E==1:
    B[j]+=1
    F=j
 C*=E
 C%=1000000007
print(C)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
fac = [1 for _ in range(n+1)]
mod = 10 ** 9 + 7

ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
# print(A)
RGB = [1,0,0]
M = 1000000007

c = 3

f = False
if A[0] != 0:
    f = True

for i in range(1,N):
    try:
        cnt = RGB.count(A[i])
        idx = RGB.index(A[i])
    except:
        f = True
        break
    c = (c * cnt)%M
    RGB[idx] += 1
    # print(RGB)
if f:
    print(0)
else:
    print(c)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = input()
A=[int(j) for j in input().split()]

nums = [0,0,0]
ans = 1
for a in A:
  ans = (ans*nums.count(a))%(10**9 +7)
  for i in range(len(nums)):
        if nums[i] == a:
            nums[i] = a+1
            break
          
print(ans)

Submission status: Accepted

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

B=[0]*(n+1)
B[0]=3
ans=1
for i in A:
    ans *=B[i]
    ans %=mod
    B[i] -=1
    B[i+1] +=1

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)



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

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

ans = 1
def dfs(i,x,y,z,a,n):
    global ans
    if i == n:
        return
    if x == y == z == a[i]:
        ans *= 3
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif x == y == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == z == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x,y + 1,z,a,n)
    elif x == a[i]:
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == a[i]:
        dfs(i + 1,x,y + 1,z,a,n)
    elif z == a[i]:
        dfs(i + 1,x,y,z + 1,a,n)
    else:
        ans = 0
        return

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

    dfs(0,0,0,0,a,n)
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    count=[3 if i==0 else 0 for i in range(N+1)]
    ans=1
    for a in A:
        ans = ans*count[a]%MOD
        if ans==0:
            break
        count[a]-=1
        count[a+1]+=1
    print(ans)

main()

Submission status: Accepted

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