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: Runtime Error

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]==0):
        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
        now[corr[0]]+=1
print(ans)

Submission status: Runtime Error

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:
        dic[a[i]] += 1
    else:
        dic[a[i]] = 0
    if a[i] == 0:
        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: Runtime Error

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

Submission status: Runtime Error

Solution code:
# なぜか途中からREなる...
n = int(input())
s = list(map(int, input().split()))
color = 0  # appeared_zero (0~2)
ans = 1
MOD = 1000000007
cur = [-1, -1, -1]
for c in s:
    if c == 0:
        cur[color] = 0
        color += 1
        ans %= MOD
    else:
        x = cur.count(c - 1)
        ans *= x
        ans %= MOD
        if c - 1 in cur:
            idx = cur.index(c - 1)
            cur[idx] += 1
        else:
            print("????????????")
            exit()
ans *= 3 if color == 0 else 3 if color == 1 else 6
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))

rgb = [0, 0, 0]
rst = 1
mod = 1000000007

for i in a:
    cnt = rgb.count(i)
    idx = rgb.index(i)
    rgb[idx] += 1

    rst *= cnt
    rst %= mod

print(rst)

Submission status: Runtime Error

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

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cur = 1
    nums = []
    for i in range(N):
        if A[i] == 0:
            cur *= 1
            nums.append(0)
            continue
        #A[i] != 0
        cnt = 0
        for j, n in enumerate(nums):
            if n == A[i] - 1:
                if cnt == 0:
                    nums[j] += 1
                cnt += 1
        cur *= cnt
        cur %= 10**9+7
        # print(nums)
    m = [3, 6, 6]
    print((cur * m[len(nums)-1]) % 10**9+7)
main()

Submission status: Runtime Error

Solution code:
n = int(input())
vals = map(int, input().split(" "))
cur_vals = [-1, -1, -1]

M = 1000000007
out = 1
for val in vals:
    before_val = val-1
    before_val_num = sum([1 for cur_val in cur_vals if cur_val == before_val])
    out = (out * before_val_num) % M
    tar_i = cur_vals.index(before_val)
    cur_vals[tar_i] = val

print(out)

Submission status: Runtime Error

Solution code:
# なぜか途中からREなる...
n = int(input())
s = list(map(int, input().split()))
color = 0  # appeared_zero (0~2)
ans = 1
MOD = 1000000007
cur = [-1, -1, -1]
for c in s:
    if c == 0:
        cur[color] = 0
        color += 1
        ans *= 3 if color == 0 else 3 if color == 1 else 6
        ans %= MOD
    else:
        x = cur.count(c - 1)
        ans *= x
        ans %= MOD
        idx = cur.index(c - 1)
        cur[idx] += 1
ans *= 3 if color == 0 else 3 if color == 1 else 6
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import collections
mod = 10 ** 9 + 7

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

# import numpy.random as rd
# n = 1000
# raw_nums = list(rd.randint(low=0, high=3, size=n))
# print(raw_nums)
# nums = [0] + [len([x for x in raw_nums[:i] if x == raw_nums[i]]) for i in range(1, n)]

# print(n, raw_nums, nums)

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * collections.Counter(n_colors)[x]) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cur = 1
    nums = []
    for i in range(N):
        if A[i] == 0:
            cur *= 1
            nums.append(0)
            continue
        #A[i] != 0
        cnt = 0
        for j, n in enumerate(nums):
            if n == A[i] - 1:
                if cnt == 0:
                    nums[j] += 1
                cnt += 1
        cur *= cnt
        cur %= 10**9+7
        # print(nums)
    m = [3, 6, 6]
    print(cur * m[len(nums)-1])
main()

Submission status: Runtime Error

Solution code:
import scipy

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(map(int, input().split()))
color = 0  # appeared_zero (0~2)
ans = 1
MOD = 1000000007
cur = [-1, -1, -1]
for c in s:
    if c == 0:
        cur[color] = 0
        color += 1
        ans %= MOD
    else:
        x = cur.count(c - 1)
        ans *= x
        ans %= MOD
        idx = cur.index(c - 1)
        cur[idx] += 1
ans *= 3 if color == 0 else 3 if color == 1 else 6
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
c = [0]*(int(input())+1)
c[-1] = 3
ans = 1
for a in list(map(int, input().split())):
    ans = (ans * (cnts[a-1] - cnts[a]))%mod
    cnts[a] += 1
print(ans)

Submission status: Runtime Error

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

ans = 3
hats = [1, 0, 0]

for a in A[1:]:
    count = hats.count(a)
    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
RGB = [0]*3
ans = 1
for i in A:
    count = 0
    for j in RGB:
        if i == j:
            count += 1
    RGB[RGB.index(i)] += 1
    ans = (ans * count)% MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def calc(mae, now):
    if mae == 3:
        if now == 0:
            return 3
        elif now == 1:
            return 2
        elif now == 2:
            return 1
    elif mae == 2:
        if now == 0:
            return 2
        elif now == 1:
            return 1
    elif mae == 1:
        if now == 0:
            return 1


if __name__ == "__main__":
    n = int(input())
    a = np.array(list(map(int, input().split())))
    mod = 10**9+7

    memo = np.zeros(n+1, dtype=int)
    memo[0] = 3
    ans = 1
    for i in a:
        mae = memo[i]
        now = memo[i+1]
        ans *= calc(mae, now)
        ans %= mod

        memo[i+1] += 1

    print(ans)

Submission status: Runtime Error

Solution code:
import collections
mod = 1000000007

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

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * collections.Counter(n_colors)[x]) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Submission status: Runtime Error

Solution code:

X = [0,0,0]

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

res = 1
for a in A:
    res = res*X.count(a) % 1000000007
    if X.count(a):
        X[X.index(a)] += 1
    else:
        assert False
print(res)

Submission status: Runtime Error

Solution code:
mod=10**9+7

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

if A.count(0)==1: # 1色のみ
    ans=3
elif A.count(0)==2: # 2色のみ
    ans=1
    c1=c2=0
    for Ai in A:
        if Ai==0:
            if c1==0:
                c1+=1
                ans=ans*3%mod
            elif c2==0:
                c2+=1
                ans=ans*2%mod
        else:
            if c1==c2==Ai:
                c1+=1
                ans=ans*2%mod
            else:
                if c1==Ai:
                    c1+=1
                elif c2==Ai:
                    c2+=1
elif A.count(0)==3: # 3色全部
    ans=1
    c1=c2=c3=0
    for Ai in A:
        if Ai==0:
            if c1==0:
                c1+=1
                ans=ans*3%mod
            elif c2==0:
                c2+=1
                ans=ans*2%mod
            elif c3==0:
                c3+=1
        else:
            if c1==c2==c3==Ai:
                c1+=1
                ans=ans*3%mod
            elif c1==c2==Ai or c1==c3==Ai:
                c1+=1
                ans=ans*2%mod
            elif c2==c3==Ai:
                c2+=1
                ans=ans*2%mod
            else:
                if c1==Ai:
                    c1+=1
                elif c2==Ai:
                    c2+=1
                elif c3==Ai:
                    c3+=1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    i=C.index(a)
    r=r*sum([1 if c==a else 0 for c in C])%m
    C[i]+=1
print(r)

Submission status: Runtime Error

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


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


a = 1
state = [0, 0, 0]

for i in range(N):
    c = state.count(A[i]) 
    a *= c
    a %= P
    state[state.index(A[i])] = A[i] + 1

print(a)

Submission status: Runtime Error

Solution code:
MOD = int(1e9+7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * 3
    ans = 1
    for a in A:
        ans = (ans * cnt.count(a)) % MOD
        c = cnt.index(a)
        cnt[c] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    N = read_int()
    A = read_ints()
    print(solve(N, A))


MOD = 1000000007


def solve(N, A):
    c = 1
    nums = [0, 0, 0]

    for a in A:
        z = nums.count(a)
        c *= z
        c %= MOD
        nums[nums.index(a)] = a + 1

    return c


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

DEBUG = 'DEBUG' in os.environ


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


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  x=RGB.count(ls[i])
  ans=(ans*x)%MOD
  y=RGB.index(ls[i])
  RGB[y]+=1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
mod = 10**9+7

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

remain = 3
s = [0,0,0]
ans = 1
for i in a:
    ans *= s.count(i)
    ans %= mod
    s[s.index(i)] += 1

print(ans)

Submission status: Runtime Error

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

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

col = [1,0,0]

ans = 3
cnt = 2

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

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    i=C.index(a)
    r=r*sum([1 if c==a else 0 for c in C])%m
    C[i]+=1
print(r)

Submission status: Runtime Error

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

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

mod=1000000007

DP=[0,0,0]
ANS=1

for a in A:
    ANS=ANS*DP.count(a)%mod
    x=DP.index(a)
    DP[x]+=1

print(ANS)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
ans=1
rgb=[0]*3
for i in range(n):
    f=0
    for i in range(3):
        if l[i]==rgb[i]:
            if f==0:
                rgb[i]+=1
            f+=1
    ans*=f
    ans%=mod
print(ans)