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: Wrong Answer

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][:])
        try:
            xyz_list[-1][xyz_list[-1].index(a)] += 1
        except ValueError:
            return -1
    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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0,0,0]
count = 1
for i in range(n):
    match = (a[i]==c[0])+(a[i]==c[1])+(a[i]==c[2])
    if match==0:
        count = 0
        break
    elif match==1 or a[i]==0:
        c[c.index(a[i])] += 1
    else:
        c[c.index(a[i])] += 1
        count = (count*match)%(1e+9+7)
               
if count != 0:
    match = (c[0]==c[1])+(c[1]==c[2])+(c[2]==c[0])
    for i in range(2,match+1):
        count = (count*i)%(1e+9+7)
        
print(int(count))

Submission status: Wrong Answer

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()))

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: Wrong Answer

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()))

MAX = 2 * 10 ** 5 + 5
# MAX = max(A) + 1
count = [0] * (MAX)
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: Wrong Answer

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()))

# MAX = 10 ** 5 + 1
MAX = max(A) + 1
count = [0] * (MAX)
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: Wrong Answer

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()))

# MAX = 10 ** 5 + 1
MAX = max(A) + 1
count = [0] * (MAX)
count[0] = 1
ans = 3
for a in A[1:]:
    if a == 0:
        ans *= 3 - count[0]
    else:
        ans *= count[a - 1] - count[a]
    count[a] += 1

MOD = 10 ** 9 + 7
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
Ali = list(map(int,input().split()))
Ali = Ali[::-1]

C = [-1,-1,-1]
r = 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
Ali = list(map(int,input().split()))
Ali = Ali[::-1]

C = [-1,-1,-1]
r = 1

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

Submission status: Wrong Answer

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
    if ans <= 0:
        print(0)
        exit()
ans *= 6 if cnt[0] > 1 else 3
print(ans % mod)

Submission status: Wrong Answer

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
    if ans < 0:
        print(0)
        exit()
ans *= 6 if cnt[0] > 1 else 3
print(ans % mod)

Submission status: Wrong Answer

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])
        if ans < 0:
            print(0)
            exit()
    cnt[a] += 1
    ans %= mod
ans *= 6 if cnt[0] > 1 else 3
print(ans % mod)

Submission status: Wrong Answer

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
ans *= 6 if cnt[0] > 1 else 3
print(ans % mod)

Submission status: Wrong Answer

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 = 3 if color == 1 else 6
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
print(ans)

Submission status: Wrong Answer

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
print(ans%mod)

Submission status: Wrong Answer

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 *= cnt
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

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 *= cnt
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(' ')))
mod = 10**9+7
high = 0
mid = 0
low = 0
ans = 1
for i in A:
    if i == high:
        if high==mid==low:
            ans *= 3
        elif high == mid:
            ans *= 2
        high += 1
    elif i == mid:
        if mid == low:
            ans *= 2
        mid += 1
    else:
        low += 1
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(' ')))
mod = 10**9+7
high = 0
mid = 0
low = 0
ans = 1
for i in A:
    if i == high:
        if high==mid==low:
            ans *= 3
        elif high == mid:
            ans *= 2
        high += 1
    elif i == mid:
        if mid == low:
            ans *= 2
        mid += 1
    else:
        low += 1
    ans %= mod
print(ans)

Submission status: Wrong Answer

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[0]==1:
  print(ans*3%mod)
elif d[0]==2:
  print(ans*6%mod)
elif d[0]==3:
  print(ans*6%mod)

Submission status: Wrong Answer

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
        d[m]+=1
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: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
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
            de=1
    pos *= pre
print(pos%(10**9+7))

Submission status: Wrong Answer

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 ng >= 2 else 3
    output *= ng
    output %= MOD
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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-1):
    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: Wrong Answer

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

Submission status: Wrong Answer

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 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: Wrong Answer

Solution code:
#from math import *
N=int(input())
A=list(map(int,input().split()))
l=[[] for _ in range(3)]
ans=1
p=10**9+7
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:
        break
    l[ind[0]].append(piv)
    ans=(ans*cnt)%p
    #print(l,ans)
    #input()
print(ans%p)

Submission status: Wrong Answer

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:
                B+=1
                count+=1
        ans*=count
        ans%=MOD
    if R>0 and G>0 and B>0:
        print(ans)
    elif R==N or G==N or B==N:
        print(ans)
    else:
        print(ans//2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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:
                B+=1
                count+=1
        ans*=count
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys

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

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: Wrong Answer

Solution code:
import sys

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

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()
        if 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]!=1:
            print(0)
            sys.exit()

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

Submission status: Wrong Answer

Solution code:
import sys

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

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]==2:
            if acnt[a[i]]==1:
                t=(t*2)%mod
        elif acnt[a[i]-1]==3:
            if acnt[a[i]]==1:
                t=(t*3)%mod
            elif acnt[a[i]]==2:
                t=(t*2)%mod
    else:
        if acnt[0]==2:
            t=(t*2)%mod

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

Submission status: Wrong Answer

Solution code:
import sys

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

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
    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]==2:
            if acnt[a[i]]==1:
                t=(t*2)%mod
        elif acnt[a[i]-1]==3:
            if acnt[a[i]]==1:
                t=(t*3)%mod
            elif acnt[a[i]]==2:
                t=(t*2)%mod
    else:
        if acnt[0]==2:
            t=(t*2)%mod

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

Submission status: Wrong Answer

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

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%mod)
#print(L)

Submission status: Wrong Answer

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

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: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
print(Counter(A))
MOD = 10 ** 9 + 7
#A.reverse()
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: Wrong Answer

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
    else:
        ans *= 6
    
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

p =10**9+7

cnt= [0]*n
cnt[0]=1
ans = 3
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: Wrong Answer

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

p =10**9+7

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

print(ans%p)

Submission status: Wrong Answer

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

p =10**9+7

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

print(ans%p)

Submission status: Wrong Answer

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

p =10**9+7

cnt= [0]*n
cnt[0]=1
ans = 3
for i in range(1,n):

    if a[i]==0:
        ans *= ((3-cnt[0])%p)
    else:
        ans *= (cnt[a[i]-1]%p - cnt[a[i]]%p)%p
    cnt[a[i]] += 1

print(ans%p)

Submission status: Wrong Answer

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: Wrong Answer

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
    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: Wrong Answer

Solution code:
from statistics import mode
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)
else:
    ans=0

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        if 1000000007<=ans:
            ans=ans%1000000007
        b.append(i)
else:
    ans=0
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)

else:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        if 1000000007<=ans:
            ans=ans%1000000007
        b.append(i)
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    
elif a.count(0)==3:
    ans=6

else:
    ans=4
print(ans%1000000007)

Submission status: Wrong Answer

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]
print(ans)

Submission status: Wrong Answer

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]
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
N=[0]*(10**6)
if len([a for a in A if a==0])==1:
    ans=3
else:
    ans=6

for a in A:
    N[a]+=1
    if a!=0:
        ans*=N[a-1]
        N[a-1]-=1
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
N=[0]*(max(A)+1)
if len([a for a in A if a==0])==1:
    ans=3
else:
    ans=6

for a in A:
    N[a]+=1
    if a!=0:
        ans*=N[a-1]
        N[a-1]-=1
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
# print(A)
RGB = [1,0,0]
M = 10**9+7

c = 3

f = False
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: Wrong Answer

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
ans=1
from collections import Counter
c=Counter()
for i in a:
    if c[i-1]==0:
        ans*=(3-c[i])
    else:
        ans*=(c[i-1]-c[i])
    c[i]+=1
    ans%=mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
C = [0]*(N+1)
C[-1] = 3
MOD = 10**9+7

res = 1
for a in A:
    C[a] += 1
    # print(min(C[a-1], 4-C[a]))
    res = res * min(C[a-1], 4-C[a]) % MOD

print(res)

Submission status: Wrong Answer

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:
    c[i + 1] += 1
    if c[i + 1] == 1:
        ans *= c[i]
    elif c[i + 1] == 2 and c[i] == 3:
        ans *= 2
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
'''
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    cnt = [3] + [0]*n
    res = 1
    for i in a:
        if cnt[i] == 3:
            res = (res * 3) % mod
        if cnt[i] == 2:
            res = (res * 2) % mod
        cnt[i] -= 1
        cnt[i+1] += 1
    print(res)
        
if __name__ == '__main__':
    main()