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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    from functools import reduce
    xyz_list = [[0]*3]
    for a in A:
        xyz_list.append(xyz_list[-1][:])
        for i, v in enumerate(xyz_list[-1]):
            if v == a:
                xyz_list[-1][i] += 1
                break
    T = [xyz.count(a) for xyz, a in zip(xyz_list, A)]
    return reduce(lambda a,b: a*b%MOD, T)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
mod=10**9+7
l=[0]*(n+1)
l[0]=3
ans=1
for ai in a:
  ans*=l[ai]
  ans%=mod
  l[ai]-=1
  l[ai+1]+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

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

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

MAX = 2 * 10 ** 5 + 5
count = [0] * N
count[0] = 1
ans = 3
MOD = 10 ** 9 + 7
for a in A[1:]:
    if a == 0:
        ans *= 3 - count[0]
    else:
        ans *= count[a - 1] - count[a]
    ans %= MOD
    count[a] += 1

print(ans % MOD)

Submission status: Accepted

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

m = 1000000007

result = 1
t = [0, 0, 0]
for i in range(N):
    a = A[i]
    f = -1
    k = 0
    for j in range(3):
        if t[j] == a:
            k += 1
            if f == -1:
                t[j] += 1
                f = j
    result *= k
    result %= m
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
color = [0, 0, 0]
ans = 1
mod = 10 ** 9 + 7
for i in a:
    cnt = color.count(i)
    ans *= cnt
    ans = ans % mod
    if ans > 0:
        color[color.index(i)] += 1
    else:
        break
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

dp = [0] * (n + 1)
dp[0] = 3
ans = 1
for x in arr:
    ans = ans * dp[x] % MOD
    # 選んだら減る
    dp[x] -= 1
    # 次に選べるようになる
    dp[x + 1] += 1

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

dic = DD(int)
dic[-1] = 3
ans = 1
for a in A:
  ans *= dic[a-1]
  ans %= 10**9+7
  dic[a] += 1
  dic[a-1] -= 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
d=[-1,-1,-1]
ans=1
for aa in a:
  ans*=d.count(aa-1)
  ans%=mod
  if aa-1 in d:
    d[d.index(aa-1)]+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dat = map(int, input().split())
dat = list(dat)
buf = [0] * 100100
buf[0] = 3
res = 1
M = (10**9 + 7)
for i in range(n):
    x = dat[i]
    res *= buf[x]
    res %= M
    buf[x] -= 1
    buf[x+1] += 1
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]

# print(cnt)

for num in nums:
    ans = ans * cnt[num] % MOD
    if ans == 0:
        break
    cnt[num] -= 1
    cnt[num + 1] += 1
# print(cnt)
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

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

Submission status: Accepted

Solution code:
import itertools

N = int(input())
Ali = list(map(int,input().split()))
C = [0,0,0]

for i in range(N):
  n = 0
  for j in range(3):
    if C[j] == Ali[i]:
      C[j] += 1
      break
  
Ali = Ali[::-1]
if C[0] == C[1] == C[2]:
  r = 1
elif C[0] == C[1] or C[1] == C[2] or C[2] == C[0]:
  r = 3
else:
  r = 6

  
for i in range(N):
  n = 0
  ta = 0 
  for j in range(3):
    if C[j]-1 == Ali[i]:
      n += 1
      ta = j
  r *= n
  C[ta] = Ali[i]
  
print(r%1000000007)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N = NI()
    A = NLI()
    nowRGB = [0, 0, 0]
    ans = 1
    for a in A:
        ans *= nowRGB.count(a) % MOD
        for i in range(3):
            if nowRGB[i] == a:
                nowRGB[i] += 1
                break

    print(ans%MOD)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9+7
    # check[i]:= Aの中のiが出てきた順番
    check = [[] for _ in range(N)]
    for i in range(N):
        check[A[i]].append(i)
    
    # print(check)
    ans = 1
    for i in range(len(check[0])):
        ans *= (3-i)

    for i in range(1,N):
        if len(check[i-1]) < len(check[i]):
            exit(print(0))
        # check[i]がcheck[i-1]のなかで何番目か調べる
        for j in range(len(check[i])):
            d = bisect_right(check[i-1],check[i][j])
            if d < j:
                exit(print(0))
            ans *= d-j
            ans %= p
            # print(ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()

numlist = [0] * N
list_zero = 3
ans = 1

for i in range(N):
    if A[i] == 0:
        ans *= list_zero
        list_zero -= 1
        numlist[0] += 1
    else:
        ans *= numlist[A[i] - 1]
        numlist[A[i] - 1] -= 1
        numlist[A[i]] += 1
    ans %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
# https://matsu7874.hatenablog.com/entry/2019/12/01/230357

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

# 先頭はr/g/b
count = [3 if i == 0 else 0 for i in range(n + 1)]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
l = [0] * 3
n = int(input())
a = [int(i) for i in input().split()]
m = 1000000007
ans = 1
for i in a:
    if(l.count(i) == 3):
        ans = ans * 3 % m
        l[0] += 1
    elif(l.count(i) == 2):
        ans = ans * 2 % m
        l = [i+1, i, sum(l)-2*i]
    elif(l.count(i) == 1):
        l[l.index(i)] += 1
    else:
        print(0)
        sys.exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
color = A.count(0)
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    else:
        ans *= (3 - cnt[a])
    cnt[a] += 1
    ans %= mod
print(ans)

Submission status: Accepted

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

dp = [[0]*3 for _ in range(N+1)]
ans = 1
for i in range(N):
    a = As[i]
    dplis = dp[i]
    cnt = 0
    dp[i+1] = dplis[:]
    for j, d in enumerate(dplis):
        if a==d:
            cnt += 1
            if cnt==1:
                dp[i+1][j] = a+1
    if cnt==0:
        print(0)
        break
    ans = ans*cnt%mod
else:
    print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def f():
    n=int(input())
    l=[0,0,0]
    ans=1
    mod=10**9+7
    for i in list(map(int,input().split())):
        if i not in l:print(0);exit()
        ans=ans*l.count(i)%mod
        l[l.index(i)]+=1
    print(ans)
if __name__ == "__main__":f()

Submission status: Accepted

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


R=[0]
G=[0]
B=[0]

#print(A)
ans=1
for i in range(N):
    tmp=0
    if A[i]==R[-1]:
        tmp+=1
    if A[i]==G[-1]:
        tmp+=1
    if A[i]==B[-1]:
        tmp+=1
    ans = (ans*tmp)%p

    if A[i]==R[-1]:
        R.append(R[-1]+1)
        G.append(G[-1])
        B.append(B[-1])
    elif A[i]==G[-1]:
        R.append(R[-1])
        G.append(G[-1]+1)
        B.append(B[-1])
    else:
        R.append(R[-1])
        G.append(G[-1])
        B.append(B[-1]+1)
    
#print(R)
#print(G)
#print(B)
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 1000000007
    n = int(input())
    cnt = [0] * (n + 2)
    cnt[0] = 3
    res = 1
    for x in input().split():
        v = int(x)
        res *= cnt[v] - cnt[v + 1]
        res %= mod
        cnt[v + 1] += 1
    print(res)

main()

Submission status: Accepted

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

print(ans % mod)

Submission status: Accepted

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

mod = 10**9 + 7
ans = 1
cnt = [0] * 3
for i in range(n):
    t = 0
    first = True
    for j in range(3):
        if cnt[j] == a[i]:
            t += 1
            if first:
                first = False
                cnt[j] += 1
    ans = (ans * t) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
r = 0
b = 0
g = 0
ans = 1
for i in range(n):
    p = 0
    if a[i] == r:
        p += 1
        r += 1
    if a[i] == b:
        p += 1
        if p == 1:
            b += 1
    if a[i] == g:
        p += 1
        if p == 1:
            g += 1
    ans *= p
    ans %= mod
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())
A = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
c = [0, 0, 0]
ans = 1
for i in A:
    ans *= c.count(i)
    if i == c[0]:
        c[0] += 1
    elif i == c[1]:
        c[1] += 1
    else:
        c[2] += 1
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
current = [-1]*3
MOD = 1000000007
res = 1
for c in a:
    cnt = 0
    for can in current:
        if can == c-1:
            cnt += 1
    for i, v in enumerate(current):
        if v == c-1:
            current[i] = c
            break

    res *= cnt
    res %= MOD

res %= MOD
print(res)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
#from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
d={x:0 for x in range(n)}
for i in range(n):
    if a[i]==0:
        d[0]+=1
    else:
        m=a[i]
        ans=(ans*(d[m-1]-d[m]))%mod
        if ans<=0:
          print(0)
          exit()
        d[m]+=1
    if d[a[i]]>3:
      print(0)
      exit()
if d[0]==1:
  print(ans*3%mod)
elif d[0]==2:
  print(ans*6%mod)
elif d[0]==3:
  print(ans*6%mod)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0:
    print(0)
    exit()
r=1
b=0
g=0
pos=3
for i in range(1,n):
    pre=0
    de=0
    if a[i]==r:
        pre += 1
        r += 1
        de=1
    if a[i]==b:
        pre += 1
        if de==0:
            b += 1
            de=1
    if a[i]==g:
        pre += 1
        if de==0:
            g += 1
    
    pos *= pre
print(pos%(10**9+7))

Submission status: Accepted

Solution code:
def col_count(A,N,M):
    col = [[0,0,0] for _ in range(N+1)]
    for i in range(N):
        for j in range(3):
            col[i+1][j] = col[i][j]
        for j in range(3):
            if col[i][j] == A[i]:
                col[i+1][j] += 1
                break

    output = 1
    for i in range(N):
        cnt = 0
        for j in range(3):
            if col[i][j] == A[i]:
                cnt += 1

        output *= cnt
        output %= M
    return output

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

    print(col_count(A,N,M))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a=int(input())
b=list(map(int,input().split()))
c=[0,0,0]
ans=1
mod=1000000007
for i in b:
  d=0
  for j in c:
    if i==j:
      d+=1
  if d==0:
    ans = 0
    break
  else:
    ans=ans*d%mod
    for j in range(3):
      if i==c[j]:
        c[j]+=1
        break
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, A = Z(), ZZ()
    cnt = [0] * (N)
    ng, output = 0, 1

    for a in A:
        if a == 0:
            ng += 1
            cnt[a] += 1
            continue
        cnt[a] += 1
        output *= cnt[a-1]
        output %= MOD
        cnt[a-1] -= 1
    ng = 6 if 2 <= ng <= 3 else 3 if ng == 1 else 0
    output *= ng
    output %= MOD
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

h = [0 for _i in range(n)]+[3]
result = 1
mod = 10**9 +7
for i in a:
    result = (result*(h[i-1]-h[i]))%mod
    h[i] += 1
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
mod=1000000007
l=list(map(int,input().split()))
me=[3]+[0]*2*n
ans=1
for x in l:
  ans=ans*me[x]%mod
  me[x]-=1
  me[x+1]+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=[[] for _ in range(3)]
ans=1
p=10**9+7
flag=1
for i in range(N):
    cnt=0
    piv=A[i]
    ind=[]
    for j in range(3):
        if len(l[j])==piv:
            cnt=cnt+1
            ind.append(j)
    if len(ind)==0:
        flag=0
        break
    l[ind[0]].append(piv)
    ans=(ans*cnt)%p
    #print(l,ans)
    #input()
if flag==1:
    print(ans%p)
else:
    print(flag)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
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('utf-8')

#2234
#import numpy as np

def main():
	n=II()
	A=LI()


	ans=1
	mod=10**9+7
	li=[3]+[0]*(n+1)

	for i in A:
		ans*=li[i]-li[i+1]
		ans%=mod
		li[i+1]+=1

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
A=[int(i) for i in input().split()]
MOD = 1000000007
ans = 1
cnt = [0]*(n+1)
cnt[0]=3

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

Submission status: Accepted

Solution code:
def main():
    import sys

    MOD = 1000000007
    N, *A = map(int, sys.stdin.buffer.read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a]
        C[a] -= 1
        C[a + 1] += 1

    print(ans % MOD)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

    MOD = 1000000007
    N, *A = map(int, sys.stdin.buffer.read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        C[a] -= 1
        C[a + 1] += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    seq = [-1] * 3
    ans = 1
    try:
        for a in A:
            ans = ans * seq.count(a - 1) % MOD
            seq[seq.index(a - 1)] = a
        print(ans)
    except:
        print(0)
        
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
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 i in range(N):
        a = A[i]
        count = 0
        if R==a:
            R+=1
            count+=1
            if G==a:
                count+=1
            if B==a:
                count+=1
        else:
            if G==a:
                G+=1
                count+=1
                if B==a:
                    count+=1
            else:
                if B==a:
                    B+=1
                    count+=1
                else:
                    print(0)
                    exit()
        ans*=count
        ans%=MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007

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

C = [0,0,0]
ans = 1
i = 0
while i < N:
  a = A[i]
  cnt = sum([1 if C[j] == a else 0 for j in range(3)])
  ans = (ans*cnt)%mod
  if C[0] == a:
    C[0] += 1
  elif C[1] == a:
    C[1] += 1
  else:
    C[2] += 1
  i += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
ans = 1
count = [0]*N
for a in A:
    if a == 0:
        ans *= (3-count[0])
        ans = ans % MOD
        count[0]+= 1
    else:
        ans *= (count[a-1]-count[a])
        ans = ans % MOD
        count[a] += 1
print(ans%MOD)

Submission status: Accepted

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

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

Submission status: Accepted

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

mod = 1000000007
ans = 1
rgb = [0, 0, 0]
for num in a:
    ans = (ans * rgb.count(num)) % mod
    if ans == 0:
        break
    index = rgb.index(num)
    rgb[index] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    d = [0, 0, 0]

    ans = 1
    for ai in a:
        ans *= d.count(ai)
        ans %= MOD
        for i in range(3):
            if d[i] == ai:
                d[i] += 1
                break

    print(ans)


if __name__ == '__main__':
    main()