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:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    C = [0, 0, 0]
    ans = 1
    for x in a:
        d = C.count(x)
        if d == 0:
            ans = 0
            break
        ans *= d
        ans %= 1000000007
        ind = C.index(x)
        C[ind] += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    A = LMIIS()
    numUsed = [0] * N
    ans = 1
    mod = 10**9 + 7
    for i in range(len(A)):
        if A[i] == 0:
            ans *= 3 - numUsed[0]
            # print(3 - numUsed[0])
            numUsed[0] += 1
        else:
            ans *= (numUsed[A[i]-1] - numUsed[A[i]])
            # print((numUsed[A[i]-1] - numUsed[A[i]]))
            numUsed[A[i]] += 1
        ans %= mod
    print(ans)

    





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n*2):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

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


print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = 1
color = 3
counter = [0 for i in range(n+1)]
for i,value in enumerate(a):
    if value == 0:
        tmp = 3 - counter[0]
    else:
        tmp = counter[value - 1] - counter[value]
    ans = ans * tmp % mod
    counter[value] += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = [int(x) for x in input().split()]
max_A = max(A)
counter = [[] for _ in range(max_A + 1)]
for i, a in enumerate(A):
    counter[a].append(i)
if any(len(counter[i]) > 3 for i in range(max_A + 1)):
    print(0)
    quit()
if any(len(counter[i]) < len(counter[i+1]) for i in range(max_A)):
    print(0)
    quit()

ans = [3, 6, 6][len(counter[0])-1]
mod = 10 ** 9 + 7
for i in range(max_A):
    cnt = 0
    for li in itertools.permutations(counter[i], len(counter[i+1])):
        cnt += all(v1 < v2 for v1, v2 in zip(li, counter[i+1]))
    ans = (ans * cnt) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N = int(input())
A =[int(i) for i in input().split()]
num_count = [0] * N
ans = 1
md = 1000000007
for i in range(N):
    num_count[A[i]] += 1
    if num_count[A[i]] > 3 :
        ans = 0
        break
    else:
        if A[i] != 0:
            if num_count[A[i]-1] == 0:
                ans = 0
                break
            else:
                ans *=  num_count[A[i]-1]-num_count[A[i]]+1
                ans = ans%md
        else:
            continue
if num_count[0] == 2:
    ans *= 6
    ans = ans%md
elif num_count[0] == 3:
    ans *= 6
    ans = ans%md
else:
    ans *= 3
    ans =ans%md
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter()
c[0] = 3
ans = 1

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

Submission status: Accepted

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

max_a = max(a)
lst = [0 for i in range(max_a+1)]

ans = 1
for i in a:
    if i == 0:
        if lst[i] == 0:
            ans = (ans * 3) % 1000000007
            lst[i] += 1
        elif lst[i] == 1:
            ans = (ans * 2) % 1000000007
            lst[i] += 1
        else:
            lst[i] += 1
        if lst[i] > 3:
            print(0)
            exit()
    else:
        if lst[i-1]-lst[i] < 1:
            print(0)
            exit()
        ans = (ans * (lst[i-1]-lst[i])) % 1000000007
        lst[i] += 1
        if lst[i] > 3:
            print(0)
            exit()

print(ans)

Submission status: Accepted

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

l = [0,0,0]

r = 1000000007

ans = 1

for i in range(n):
    if a[i] == l[0]:
        if a[i] == l[1]:
            if a[i] == l[2]:
                ans *= 3
            else:
                ans *= 2
        l[0] += 1
    elif a[i] == l[1]:
        if a[i] == l[2]:
            ans *= 2
        l[1] += 1
    elif a[i] == l[2]:
        l[2] += 1
    else:
        ans = 0
    ans %= r

print(ans)

Submission status: Accepted

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

c=[0,0,0]
ans=1
mod=1000000007
out=0
for aa in a:
    if aa-1 in c:
        ans = ans*c.count(aa-1) %mod
        c[c.index(aa-1)]+=1
    else:
        out=1
        break
if out==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))

cnt = {i:0 for i in range(-1,n+1)}

cnt[-1] = 3
ans = 1
mod = 10**9+7
for i in range(n):
    ans *= min(cnt[a[i]-1],cnt[a[i]-1]-cnt[a[i]])
    ans %= mod
    cnt[a[i]]+=1
    if cnt[a[i]-1]<cnt[a[i]]:
        print(0)
        exit()

print(ans)

Submission status: Accepted

Solution code:

N=int(input())

A=[int(i) for i in input().split()]


c=[0,0,0]
ans=1
uncho=True

for i in range(N):
    s=sum([c[j]==A[i] for j in range(0,3)])
    if s==0:
        uncho=False
        print(0)
        break
    c[c.index(A[i])]+=1
    ans=(ans*s)%1000000007

if uncho:
    print(ans%1000000007)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=1
li=[0,0,0]
for i in range(n):
    x*=li.count(a[i])
    for j in range(3):
        if li[j]==a[i]:
            li[j]+=1
            break 
print(x%1000000007)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ls=[0,0,0]
cnt=1
for i in range(N):
  c=0
  flag=False
  for j in range(3):
    if A[i]==ls[j]:
      c+=1
      if flag==False:
        ls[j]+=1
        flag=True
  cnt=cnt*c
print(cnt%1000000007)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    zeros = A.count(0) 
    if zeros==0 or A[0]!=0 or zeros>=4:
        print(0)
        return 
    elif zeros==1:
        ans = 3
    else:
        ans = 6
    cnt = defaultdict(int)
    cnt2 = defaultdict(int)
    for a in A:
        if a==0:
            cnt[0]+=1
            continue
        ans *= cnt[a-1]
        ans %= mod
        cnt[a-1]-=1
        cnt[a]+=1
        cnt2[a]+=1
        if cnt2[a]>3:
            ans = 0
        # print(a,ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, A):
    M = Mod(1000000007)
    ans = 1
    rem = Counter()
    c = 0
    for a in A:
        if a == 0:
            c +=1
        if rem[a-1] > 0:
            ans = M.mul(ans, rem[a-1])
            rem[a-1] -= 1
        elif a != 0 and rem[a-1] == 0:
            return 0
        rem[a] += 1

    if c > 3:
        return 0
    if c == 1:
        ans = M.mul(ans, 3)
    else:
        ans = M.mul(ans, 6)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
l = list(map(int, input().split()))

pos = [0 for _ in range(100002)]
pos[0] = 3

ans = 1

MOD = 1000000007

for i in l:
    if pos[i+1] >= 3:
        print(0)
        sys.exit()

    if pos[i] == 0:
        print(0)
        sys.exit()

    ans *= pos[i]
    ans = ans % MOD
    pos[i] -= 1
    pos[i+1] += 1

print(ans)

Submission status: Accepted

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

cur = [0,0,0]

dp = [0 for i in range(N+1)]
dp[0] = 1
for i, a in enumerate(A):

    cnt = 0
    for c in cur:
        if c==a:
            cnt+=1

    for i_c in range(3):
        if cur[i_c]==a:
            cur[i_c] += 1
            break
    dp[i+1] = (cnt*dp[i])%MOD

    # print(cur)

print(dp[N])

Submission status: Accepted

Solution code:
MOD = 1000000007

num = int(input())
arr = map(int, input().split())

group_1 = 0
group_2 = 0
group_3 = 0

ans = 1

for item in arr:
    num_choice = int(group_1 == item) + int(group_2 == item) + int(group_3 == item)
    ans *= num_choice
    ans %= MOD

    if group_1 == item:
        group_1 += 1
    elif group_2 == item:
        group_2 += 1
    elif group_3 == item:
        group_3 += 1
    else:
        print("0")
        exit(0)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
n1=-1
n2=-1
n3=-1
ans=1
mod=1000000007
b=True
for i in range(n):
  num=l[i]
  if num==n1+1 and num==n2+1 and num==n3+1:
    ans=(ans*3)%mod
    n1+=1
  elif num==n1+1 and num==n2+1:
    ans=(ans*2)%mod
    n1+=1
  elif num==n2+1 and num==n3+1:
    ans=(ans*2)%mod
    n2+=1
  else:
    if num==n1+1:
      n1+=1
    elif num==n2+1:
      n2+=1
    elif num==n3+1:
      n3+=1
    else:
      b=False
      break
if b:    
  print(ans%mod)
else:
  print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
if A[0] != 0:
    print(0)
    exit()
ans = 1
g0 = 0
g1 = 0
g2 = 0
for a in A:
    if g0==g1==g2:
        if a == g0:
            ans = (ans*3)%M
            g0 += 1
        else:
            ans = 0
    elif g0==g1:
        if a == g0:
            ans = (ans*2)%M
            g0 += 1
        elif a == g2:
            g2 += 1
        else:
            ans = 0
    elif g1==g2:
        if a == g0:
            g0 += 1
        elif a == g1:
            ans = (ans*2)%M
            g1 += 1
        else:
            ans = 0
    else:
        if a == g0:
            g0 += 1
        elif a == g1:
            g1 += 1
        elif a == g2:
            g2 += 1
        else:
            ans = 0
print(ans%M)

Submission status: Accepted

Solution code:
input()
I=list(map(int,input().split()))
L=[0,0,0]
a=1
m=10**9+7
for i in I:
  if i in L:
  	a*=L.count(i)
  	L[L.index(i)]+=1
  	a%=m
  else:
    a=0
    break
print(a)

Submission status: Accepted

Solution code:
import math

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

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

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

phase = 0
now = [0,0,0]
ans=1

for i in range(n):
    if(a[i]==-1):
        now[phase]=1
        ans*=3-phase
        ans%=1000000007
        phase+=1
    else:
        corr = []
        for j in range(3):
            if(now[j]==a[i]):
                corr.append(j)
        ans*=len(corr)
        ans%=1000000007
        if(len(corr)!=0):
            now[corr[0]]+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

hat_list = [0] * 100000

result = 1

for a in As:
    pre_hat = hat_list[a-1]
    if a == 0:
        pre_hat = 3
    hat = hat_list[a]

    result *= (pre_hat - hat)
    result %= 1000000007
    hat_list[a] += 1

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = {i : 0 for i in range(n+1)}
ct[0] = 3
MOD = 10**9+7
res = 1
for a in a_ls:
    res = res * ct[a] % MOD
    ct[a] -= 1
    ct[a+1] += 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = [0, 0, 0]
MOD = 10 ** 9 + 7
ans = 1
for i, ai in enumerate(a):
    flag = False
    x = 0
    for j, cj in enumerate(c):
        if cj == ai:
            x += 1
            if not flag:
                flag = True
                c[j] += 1
    ans *= x
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
acc = 1
b = [0,0,0]
for i in range(n):
    cnt = 0
    done = False
    for j in [0,1,2]:
        if a[i]==b[j]:
            cnt += 1
            if not done:
                b[j] += 1
                done = True
    acc = (acc * cnt) % R
print(acc)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
answer = 1
count = [0] * 3
color = []
for i in range(n):
    pcount=0
    flag=0
    if count[0] == a[i]:
        pcount+=1
        flag=1
    if count[1] == a[i]:
        pcount+=1
        flag=2
    if count[2] == a[i]:
        pcount+=1
        flag=3
    color.append(pcount)
    count[flag-1]+=1
for i in range(n):
    answer=answer*color[i]
print(answer%(10**9+7))

Submission status: Accepted

Solution code:

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

colors = [0,0,0]
ans = 1
MOD = 10**9+7
for a in A:
    tmp = 0
    for i in range(3):
        if colors[i]==a:
            if tmp==0:
                colors[i]+=1
            tmp += 1
    ans *= tmp
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
mx = max(a)
lst = [3] + [0] * mx
ans = 1
for x in a:
  ans = ans * lst[x] % mod
  lst[x] -= 1
  if x < mx:
    lst[x+1] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = [int(c) for c in input().split()]
MOD = 10**9 + 7
dic = [0,0,0]
ans = 1
for i in range(N):
  x = a[i]
  m = 0
  n = 0
  for j in range(3):
    if dic[j]==x:
      n = j
      m += 1
  ans *= m
  ans %= MOD
  dic[n] += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a = list(map(int, input().split()))
dic={}
mul = [3,2,1]
res = 1
for i in range(len(a)):
    if a[i] in dic:
        if dic[a[i]] == 2:
            print(0)
            exit()
        dic[a[i]] += 1
    else:
        dic[a[i]] = 0
    if a[i] == 0:
        if dic[0] >= 3:
            print(0)
            exit()
        res *= mul[dic[0]]
    else:
        if a[i]-1 not in dic:
            print(0)
            exit()
        res *= dic[a[i]-1] - dic[a[i]] + 1
    res = res%(10**9+7)
print(res)

Submission status: Accepted

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

temp2 = 0
temp1 = 0

cand = [0] * (N+1)
cand[0] = 3
ret = 1
for i in range(N):
    ret *= cand[A[i]]
    cand[A[i]+1] += 1
    cand[A[i]] -= 1

print(ret % MOD)

Submission status: Accepted

Solution code:
n = int(input())
a = list(int(x) for x in input().split())

ans = 1
key = [0, 0, 0]
for i in range(n):
    k = a[i]
    p = 0
    q = 0
    if key[0] == k:
        p += 1
        q = 1
    if key[1] == k:
        p += 1
        if q == 0:
            q = 2
    if key[2] == k:
        p += 1
        if q == 0:
            q = 3
    ans = (ans*p)%1000000007
    key[q-1] = key[q-1]+1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
#print(a) 
x=0;y=0;z=0
c=0;d=0;e=0
ss=[[0,0,0] for _ in range(n)]
ans=1
for i in range(n):
    if a[i]==c:
        l[i]='r'
        c+=1
    elif a[i]==d:
        l[i]='b'
        d+=1
    elif a[i]==e:
        l[i]='g'
        e+=1
    ss[i][0]=c;ss[i][1]=d;ss[i][2]=e
ss=[[0,0,0]]+ss
#print(ss)
p=[0,0,0]
for i in range(1,n+1):
    p[0]=ss[i][0]-ss[i-1][0];p[1]=ss[i][1]-ss[i-1][1];p[2]=ss[i][2]-ss[i-1][2]
    #print(p)
    if ss[i-1][0]==ss[i-1][1]==ss[i-1][2] and p[0]==1:
        ans=ans*3%(10**9+7)
    elif ss[i-1][0]==ss[i-1][1] and p[0]==1:
        ans=ans*2%(10**9+7)
    elif ss[i-1][1]==ss[i-1][2] and p[1]==1:
        ans=ans*2%(10**9+7)
    if p==[0,0,0]:
        ans=0
        break
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

S = [0]*3
total = 1
for i in range(N):
    count = 0
    flag=0
    for j in range(3):
        if S[j]==A[i]:
            count += 1
            if flag==0:
                S[j] += 1
                flag=1
    total = (total*count)%1000000007
    
print(total)

Submission status: Accepted

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

MOD=10**9+7

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

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7

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

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

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

    print(ret)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 1
c = [0] * 100010
c[0] = 3
for i in range(n):
    ans *= c[a[i]] - c[a[i] + 1]
    ans %= MOD
    c[a[i] + 1] += 1
print(ans)

Submission status: Accepted

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

ans = 1
c = [0, 0, 0]
for i in range(N):
    n = c.count(A[i])
    ans *= n
    ans %= MOD
    if n > 0:
        c[c.index(A[i])] += 1
print(ans)

Submission status: Accepted

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

color=[0,0,0]
chance=1
for i in range(N):
  chance*=color.count(A[i])
  #print(chance)
  #print(color)
  for j in range(3):
    if A[i]==color[j]:
      color[j]+=1
      break
print(chance%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
c = [0,0,0]
pos = True
for h in range(len(a)):
    try:
        n = a[h]
        a[h] = c.count(n)
        c[c.index(n)] += 1
    except:
        pos = False
        break
# print(a)
# print(c)
if pos:
    c = 1
    for n in a:
        c *= n%1000000007
    print(c%1000000007)
else:
    print(0)

Submission status: Accepted

Solution code:
1000000007
r = -1
g = -1
b = -1
N = int(input())
A = input().split()
A = [int(a) for a in A]

mul = 1
for i in range(N):
    
    same = 0
    same_c = 0
    
    if(r==A[i]-1):
        same += 1
        same_c = 1
    if(g==A[i]-1):
        same += 1
        same_c = 2
    if(b==A[i]-1):
        same += 1
        same_c = 3
        
    if(same_c==1):
        r = A[i]
    elif(same_c==2):
        g = A[i]
    elif(same_c==3):
        b = A[i]
        
    mul *= same
    mul = mul%1000000007
    
    
print(mul)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
hat = [0,0,0]
ans = 1
#red blue green
for i in range(N):
  if A[i] == hat[0]:   
    hat[0] += 1
    if A[i] == hat[1]:
      if A[i] == hat[2]:
        ans *= 3
      else:
        ans *= 2
  elif A[i] == hat[1]:
    hat[1] += 1
    if A[i] == hat[2]:
      ans *= 2
  elif A[i] == hat[2]:
    hat[2] += 1
    ans *= 1
  else:
    #print(hat, i)
    ans = 0
    print(ans)
    quit()
  #print(ans)
print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = count = 0; pro = 1

n=int(input())
A=list(map(int,input().split()))
data=[0]*(10**5+1)
for i in range(n):
    if A[i]==0:
        pro*=3-data[0]
    else:
        # print(pro)
        # print(data[:10])
        # print(data[A[i]-1]-data[A[i]])
        pro*=data[A[i]-1]-data[A[i]]
    data[A[i]]+=1
    pro=pro%mod
# print(data[:10])
print(pro%mod)

Submission status: Accepted

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

useList = [0] * 3
result = 1

for i, a in enumerate(aList):
  result = (result * useList.count(a)) % 1000000007
  if useList[0] == a:
    useList[0] += 1
  elif useList[1] == a:
    useList[1] += 1
  else:
    useList[2] += 1

print(result)

Submission status: Accepted

Solution code:
MOD = 10**9+7

N = int(input())
count = [0] * 3
ans = 1

A = [int(x) for x in input().split()]

for i in range(N):
    sames = 0
    for j in range(3):
        if A[i] == count[j]:
            sames += 1

    if sames == 0:
        ans = 0
        break

    ans *= sames
    ans %= MOD

    for j in range(3):
        if A[i] == count[j]:
            count[j] += 1
            break
print(ans)

Submission status: Accepted

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

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 = (result * k) % 1000000007
print(result)

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    a = list(map(int, input().split()))
    if a[0] != 0:
        print(0)
        exit()
    ans = 1
    r,g,b = 0,0,0
    for i in range(n):
        if i == 0:
            r += 1
            ans = 3
        else:
            cnt = 0
            f = True
            if r == a[i]:
                cnt += 1
                r += 1
                f = False
            if g == a[i] :
                cnt += 1
                if f:
                    g += 1
                f = False
            if b == a[i] :
                cnt += 1
                if f:
                    b += 1

            
            ans = (ans * cnt) % MOD
    print(ans % MOD)            
            




    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
ans = 1
colors = [-1, -1, -1]  # red, blue, green
for i in range(N):
    flag = [False] * 3
    cnt = 0
    # print(A[i]-1)
    for j in range(len(colors)):
        if A[i]-1 == colors[j]:
            flag[j] = True
            cnt += 1
    # if cnt == 0:
    #     print(0)
    #     exit()
    for k in range(3):
        if flag[k]:
            colors[k] += 1
            break
    # print(cnt)
    ans *= cnt % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]+=1
mod=10**9+7
iro=[0]*(10**5+3)
iro[0]=3
ans=1
for i in range(n):
    ans%=mod
    # print(iro[a[i]-1])
    # print(iro[a[i]])
    if iro[a[i]]==0:
        if iro[a[i]-1]==0:
            print(0)
            quit()
        else:
            ans*=iro[a[i]-1]
    elif iro[a[i]]==1:
        if iro[a[i]-1]<=1:
            print(0)
            quit()
        else:
            ans*=iro[a[i]-1]-1
    elif iro[a[i]]==2:
        if iro[a[i]-1]<=2:
            print(0)
            quit()
        else:
            ans*=1
    else:
        print(0)
        quit()
    iro[a[i]]+=1
print(ans%mod)

Submission status: Accepted

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

li = [0]*n

ans = 1
mod = 1000000007

for i in a:
    if i == 0:
        if li[0] == 0:
            ans *= 3
        elif li[0] == 1:
            ans *= 2
        elif li[0] == 2:
            ans *= 1
        else:
            ans *= 0
        li[0] += 1
    else:
        if li[i] == 0:
            if li[i-1] == 1:
                ans *= 1
            elif li[i-1] == 2:
                ans *= 2
            elif li[i-1] == 3:
                ans *= 3
            else:
                ans *= 0
        elif li[i] == 1:
            if li[i-1] == 2:
                ans *= 1
            elif li[i-1] == 3:
                ans *= 2
            else:
                ans *= 0
        elif li[i] == 2:
            if li[i-1] == 3:
                ans *= 1
            else:
                ans *= 0
        else:
            ans *= 0
        li[i] += 1
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N  = int(input())
A_list = list(input().split())
Colors = [0]*3
output = 1
for i in range(N):
    a = int(A_list[i])
    num = Colors.count(a)
    for j in range(3):
        if a == Colors[j]:
            Colors[j] += 1
            break
    output *= num
output = int(output%1000000007)
print(output)

Submission status: Accepted

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

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