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:
n=int(input())
alist=[int(i) for i in input().split()]

zeros=0
answer=1
triple=[0,0,0]

for i in range(n):
    now=alist[i]
    if now==triple[0]:
        if now==triple[1]:
            if now==triple[2]:
                answer*=3
            else:
                answer*=2
        triple[0]+=1
    else:
        if now==triple[1]:
            if now==triple[2]:
                answer*=2
            triple[1]+=1
        else:
            triple[2]+=1
    answer%=(1000000007)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import collections
n  =int(input())
a = input().split()
c = collections.Counter(a)
if c["0"]==1:
  print(3)
  sys.exit()
elif c["0"]==2:
  ans = sum(1 for x in c.items() if x[1]==2)
  coeff = 2 if sum(1 for x in c.items() if x[1]==1)>0 else 1
  print((3*2**ans*coeff)%1000000007)
else:
  ans1 = sum(1 for x in c.items() if x[1]==2)
  ans2 = sum(1 for x in c.items() if x[1]==3)
  if ans1==0:
    coeff = 3 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((6**ans2*coeff)%1000000007)
  elif ans2==0:
    coeff = 2 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((3*2**ans1**coeff)%1000000007)
  else:
    coeff = 2 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((3*2**ans1*coeff * 6**ans2)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import collections
n  =int(input())
a = input().split()
c = collections.Counter(a)
if c["0"]==1:
  print(3)
  sys.exit()
elif c["0"]==2:
  ans = sum(1 for x in c.items() if x[1]==2)
  coeff = 2 if sum(1 for x in c.items() if x[1]==1)>0 else 1
  print((2**ans*coeff)%1000000007)
else:
  ans1 = sum(1 for x in c.items() if x[1]==2)
  ans2 = sum(1 for x in c.items() if x[1]==3)
  if ans1==0:
    coeff = 3 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((6**ans2*coeff)%1000000007)
  elif ans2==0:
    coeff = 2 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((2**ans1**coeff)%1000000007)
  else:
    coeff = 3 if sum(1 for x in c.items() if x[1]==1)>0 else 1
    print((2**ans1*coeff * 6**ans2)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import collections
n  =int(input())
a = input().split()
c = collections.Counter(a)
if c["0"]==1:
  print(3)
  sys.exit()
elif c["0"]==2:
  ans = sum(1 for x in c.items() if x[1]==2)
  print((2**ans*3)%1000000007)
else:
  ans1 = sum(1 for x in c.items() if x[1]==2)
  ans2 = sum(1 for x in c.items() if x[1]==3)
  coeff = 3 if sum(1 for x in c.items() if x[1]==1)>0 else 1
  if ans1==0:
    print((6**ans2*coeff)%1000000007)
  elif ans2==0:
    print((2**ans1**coeff)%1000000007)
  else:
    print((2**ans1*coeff * 6**ans2)%1000000007)

Submission status: Wrong Answer

Solution code:
import collections
n  =int(input())
a = input().split()
c = collections.Counter(a)
if c["0"]==1:
  print(3)
elif c["0"]==2:
  ans = sum(1 for x in c.items() if x[1]==2)
  print((2**ans*3)%1000000007)
else:
  ans1 = sum(1 for x in c.items() if x[1]==2)
  ans2 = sum(1 for x in c.items() if x[1]==3)
  if ans1==0:
    print((6**ans2)%1000000007)
  elif ans2==0:
    print((2**ans1*3)%1000000007)
  else:
    print((2**ans1*3 * 6**ans2)%1000000007)

Submission status: Wrong Answer

Solution code:
#coding:utf-8

cnt = 3
colors = [1, 0, 0]

n = int(input())
data = list(map(int, input().split(" ")))

for i in range(1, n):
    num = data[i]
    if colors.count(num) == 1:
        for j in range(3):
            if colors[j] == num:
               colors[j] += 1
               break
    elif colors.count(num) == 2:
        for j in range(3):
            if colors[j] == num:
                colors[j] += 1
                cnt *= 2
                cnt %= 1000000007 
                break 
    else:
        colors[0] += 1
        cnt *= 3
        cnt %= 1000000007

print(cnt)

Submission status: Wrong Answer

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

ptn = [0] * (max(a) + 1)
ans = 1
kind = 1
for i in a:
    if i == 0:
        ptn[0] += 1
    else:
        ans *= ptn[i - 1]
        ptn[i - 1] -= 1
        ptn[i] += 1
    kind = max(kind, ptn[i])

for i in range(kind):
    ans *= (3 - i)

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
mod=10**9+7
x=[0]*(n+1) # 分布

x[0]=3
ans=1

for i in range(n):
    if x[a[i]]>0:
        ans*=x[a[i]]
        ans%=mod
        x[a[i]]-=1
        x[a[i]+1]+=1
        
    
    elif a[i]!=0:
        if x[a[i]-1]>0:
            ans*=x[a[i]-1]
            ans%=mod
            x[a[i]-1]-=1
            x[a[i]-1]+=1
        
        else:
            print(0)
            exit()

    else:
        print(0)
        exit()


print(ans)

Submission status: Wrong Answer

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = inputIntList()

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

    ret = 1
    for a in A:
        ret *= pattern[a]
        pattern[a] -= 1
        pattern[a + 1] += 1
        # print(pattern)
    return ret


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
M=1000000007

N = int(input())
A = [-1] + list(map(int,input().split()))

x = [0]*(N+1)
y = [0]*(N+1)
z = [0]*(N+1)
ans=1

for i in range(1,N+1):
    if A[i] == x[i-1] and A[i] == y[i-1] and A[i] == z[i-1]:
        ans = (ans * 3) %M
    elif A[i] == x[i-1] and A[i] == y[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == y[i-1] and A[i] == z[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == z[i-1] and A[i] == x[i-1]: 
        ans = (ans * 2) %M
    if A[i] == x[i-1]:
        x[i]=x[i-1]+1
        y[i]=y[i-1]
        z[i]=z[i-1]
    elif A[i] == y[i-1]:
        x[i]=x[i-1]
        y[i]=y[i-1]+1
        z[i]=z[i-1]
    else:
        x[i]=x[i-1]
        y[i]=y[i-1]
        z[i]=z[i-1]+1

print(ans)

Submission status: Wrong Answer

Solution code:
dummy="""
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
"""

if 0:
    def sub_get_line():
        for i in dummy.split("\n"):
            yield i
    get_line = sub_get_line().__next__
    get_line()
else:
    get_line = input

N = int(get_line())
A = [int(_) for _ in get_line().split(" ")]
N = len(A)

class B(object):
    def __init__(self):
        self.count = 0
        self.index = ()
    def __add__(self, v):
        self.count += 1
        self.index += (v,)
        return self

class Histogram(list):
    def __init__(self, v):
        list.__init__(self, v)
    def count(self, v):
        c = 0
        for i in self:
            if i.count == v:
                c += 1
        return c

histogram = Histogram([B() for i in range(N+1)])
for index, a in enumerate(A):
    histogram[a] += 1
    histogram[a+1] += 0

result = {}
ret = 1
for i in range(1, N):
    a = histogram[i]
    if a.index in result:
        #print (result[a])
        ret *= result[a.index]
        continue
    if a.count == 0:
        #print (i)
        break
    count = 0
    dd = 1
    for j in a.index:
        if j == 0:
            count += 1
        else:
            dd *= count
            count -= 1
    #print (dd, a.index)
    result[a.index] = dd
    ret *= dd
    ret %= 1000000007

if histogram[0].count == 0:
    ret = 0
elif histogram[0].count == 1:
    ret *= 3
else:
    ret *= 6

print (ret%1000000007)

Submission status: Wrong Answer

Solution code:
dummy="""
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
"""

if 1:
    def sub_get_line():
        for i in dummy.split("\n"):
            yield i
    get_line = sub_get_line().__next__
    get_line()
else:
    get_line = input()

N = int(get_line())
A = [int(_) for _ in get_line().split(" ")]
N = len(A)

class B(object):
    def __init__(self):
        self.count = 0
        self.index = ()
    def __add__(self, v):
        self.count += 1
        self.index += (v,)
        return self

class Histogram(list):
    def __init__(self, v):
        list.__init__(self, v)
    def count(self, v):
        c = 0
        for i in self:
            if i.count == v:
                c += 1
        return c

histogram = Histogram([B() for i in range(N+1)])
for index, a in enumerate(A):
    histogram[a] += 1
    histogram[a+1] += 0

result = {}
ret = 1
for i in range(1, N):
    a = histogram[i]
    if a.index in result:
        #print (result[a])
        ret *= result[a.index]
        continue
    if a.count == 0:
        #print (i)
        break
    count = 0
    dd = 1
    for j in a.index:
        if j == 0:
            count += 1
        else:
            dd *= count
            count -= 1
    #print (dd, a.index)
    result[a.index] = dd
    ret *= dd
    ret %= 1000000007

if histogram[0].count == 0:
    ret = 0
elif histogram[0].count == 1:
    ret *= 3
else:
    ret *= 6

print (ret%1000000007)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#三井住友信託銀行プログラミングコンテスト2019 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()

cnt = [0]*n
cnt[0] = 1
x = 3
tmp = 2
for i in range(1,n):
    if a[i] == 0:
        x *= tmp
        x %= mod
        tmp -= 1
    else:
        x *= cnt[a[i]-1]
        x %= mod
        cnt[a[i]-1] -= 1
    cnt[a[i]] += 1
print(x)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (max(A) + 1)
ans = 1
for a in A:
    if a > 0:
        ans *= counts[a - 1]
        ans %= MOD
        counts[a - 1] -= 1
    counts[a] += 1
if A.count(0) == 1:
    print(ans * 3 % MOD)
else:
    print(ans * 6 % MOD)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (max(A) + 1)
ans = 1
for a in A:
    if a > 0:
        ans *= counts[a - 1]
        ans %= MOD
        counts[a - 1] -= 1
    counts[a] += 1
if A.count(0) == 1:
    print(ans * 3)
else:
    print(ans * 6)

Submission status: Wrong Answer

Solution code:
mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    # ele in cur can choose ele in last which is smaller than it
    # person says i can choose person says i-1 who is in front of him
    # cur and last are naturally increase order
    ans = 1
    minus = 0
    for i in cur:
        count = 0
        for j in last:
            if j < i:
                count += 1
        ans *= count-minus
        minus += 1
    return ans
    # j = 0
    # ans = 1
    # for i in range(len(cur)):
    #     while j < len(last):
    #         if last[j] < cur[i]:
    #             j += 1
    #         else:
    #             break
    #     ans *= (j-i)
    # return ans

memo.append([-1,-1,-1]) # for convenience
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    if len(memo[i]) == 1:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    # ele in cur can choose ele in last which is smaller than it
    # person says i can choose person says i-1 who is in front of him
    # cur and last are naturally increase order
    j = 0
    ans = 1
    for i in range(len(cur)):
        while j < len(last):
            if last[j] < cur[i]:
                j += 1
            else:
                break
        ans *= (j-i)
    return ans

memo.append([-1,-1,-1]) # for convenience
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    if len(memo[i]) == 1:
        break

print(ans)

Submission status: Wrong Answer

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

x = 0
y = 0
z = 0
ans = 1
mod = 10 ** 9 + 7

for a in A:
  if a == x:
    if x == y:
      if y == z:
        ans *= 3
      else:
        ans *= 2
    x += 1
  elif a == y:
    if y == z:
      ans *= 2
    y += 1
  else:
    z += 1
ans %= mod
print(ans)

Submission status: Wrong Answer

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

x = 0
y = 0
z = 0
ans = 1
mod = 10 ** 9 + 7

for i in range(n):
  if a[i] == x:
    if x == y:
      if y == z:
        ans *= 3
      else:
        ans *= 2
    x += 1
  elif a[i] == y:
    if y == z:
      ans *= 2
    y += 1
  else:
    z += 1
ans %= mod
print(ans)

Submission status: Wrong Answer

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

x = 0
y = 0
z = 0
ans = 1

for i in range(n):
  if a[i] == x:
    if x == y:
      if y == z:
        ans *= 3
      else:
        ans *= 2
    x += 1
  elif a[i] == y:
    if y == z:
      ans *= 2
    y += 1
  else:
    z += 1
ans %= 1000000007
print(ans)

Submission status: Wrong Answer

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

x = 0
y = 0
z = 0
ans = 1

for i in range(n):
  if a[i] == x:
    if x == y == z:
      ans *= 3
    elif x == y != z:
      ans *= 2
    x += 1
  elif a[i] == y:
    if y == z:
      ans *= 2
    y += 1
  else:
    z += 1
ans %= 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = 0
y = 0
z = 0
ans = 1 
for i in range(n): #1文字目
  if a[i] == x:
    if x == y:
      if x == z:
        ans = ans * 3
      else:
        ans = ans * 2
    x = x + 1
  elif a[i] == y:
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
  	z = z + 1
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

c = [0] * (N+1)
ans = 1
for i in range(N):
    if A[i]-1 >= 0:
        ans *= c[A[i]-1] - c[A[i]]
    c[A[i]] += 1

color = []
for i in range(N):
    res = c[i] - c[i+1]
    for _ in range(res):
        color.append(i+1)
    if len(color) == 3:
        break

color += [0] * (3-len(color))
if len(set(color)) == 1:
    ans *= 3*2*1
else:
    ans *= 3

ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
c[0]=1
cnt=3
for i in a[1:]:
  if i==0:
    cnt*=3-c[0]
    c[0]+=1
  else:
    cnt*=c[i-1]-c[i]
    c[i]+=1

print(cnt%1000000007)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

def judge(n):
    j = 0
    for i in range(N):
        if S[i] == n[j]:
            j += 1
        if j == 3:
            return True
    return False

ans = 0

for num in range(1000):
    num = str(num)
    num = "0" * (3-len(num)) + num
    if judge(num):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input()) #長さ
a = input().split() #帽子の数
x = 0
y = 0
z = 0
ans = 1
 
for i in range(n): #1文字目
  if a[i] == str(x):
    if x == y == z:
      ans = ans * 3
    elif x == y != z:
      ans = ans * 2
    x = x + 1
  elif a[i] == str(y):
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input()) #長さ
a = input().split() #帽子の数
x = 0
y = 0
z = 0
ans = 1
 
for i in range(n): #1文字目
  if a[i] == str(x):
    if x == y and x == z:
      ans = ans * 3
    elif x == y and x != z:
      ans = ans * 2
    x = x + 1
  elif a[i] == str(y):
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input()) #長さ
a = input().split() #帽子の数
x = 0
y = 0
z = 0
ans = 1
 
for i in range(n): #1文字目
  if a[i] == str(x):
    if x == y and x == z:
      ans = ans * 3
    elif x == y:
      ans = ans * 2
    x = x + 1
  elif a[i] == str(y):
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3 or len(li[0])==0:
		print(0)
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6
		
	for i in range(1,aa+1):
		if len(li[i])>3 or len(li[i])==0 or li[i-1][0]>li[i][0]:
			print(0)
			exit(0)
		else:
			k=bisect.bisect_right(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_right(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3 or len(li[0])==0:
		print(0)
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6
	for i in range(1,aa+1):
		if len(li[i])>3 or len(li[i])==0:
			print(0)
			exit(0)
		else:
			k=bisect.bisect_right(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_right(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = max(a)
mod = 1000000007
memo = [[] for i in range(m+1)]
d = {}
for ai in a:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1
    if ai - 1 in d:
        memo[ai].append(d[ai-1])
    else:
        memo[ai].append(3)
ans = 1
for l in memo:
    i = 0
    for li in l:
        ans = ans * (li - i) %  mod
        i += 1
print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7

ans = 3
dp = [1,0,0]
for a in A[1:]:
    ans *= dp.count(a)
    ans %= mod
    if ans == 0: break
    dp[dp.index(a)] += 1
print(ans)

Submission status: Wrong Answer

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

mod=1000000007
cs=[0]*3
ans=1
for a in A:
  c=cs.count(a)
  if c==0:
    print()
    exit()
  ans=(ans*c)%mod
  i=cs.index(a)
  cs[i]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N = int(input())
A = list(map(int,input().split()))
r = 0
b = 0
g = 0
rr = 0
bb = 0
gg = 0
for i in range(N):
    if A[i] == rr:
        rr += 1
    elif A[i] == bb:
        bb += 1
    else:
        gg += 1
c = {rr,bb,gg}
cc = len(c)
print((((combinations_count(N, rr)%(10**9+7))*(combinations_count(N-rr, bb)%(10**9+7))*(combinations_count(N-rr-bb, gg)%(10**9+7))*combinations_count(3,cc-1))%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
a,b,c=0,0,0
w=1
for i in A:
  if i==a:
    a+=1
    if a-1==b==c:w*=3
    elif a-1==b:w*=2
  elif i==b:
    b+=1
    if b-1==c:w*=2
  elif i==c:c+=1
  w=w%(10e9+7)
print(int(w))

Submission status: Wrong Answer

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

_n = int(input())
_alist = list(map(int, input().split()))
m = 10 ** 9 + 7


def chker(n, alist):
    ans = 3
    xyz = [1, 0, 0]
    for ai in alist[1:]:
        ti = xyz.count(ai)
        ans = ans * ti % m
        for i in range(3):
            if xyz[i] == ai:
                xyz[i] += 1
                break

        xyz.sort(reverse=True)

    print(ans)


chker(_n, _alist)

Submission status: Wrong Answer

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N=int(input())
A=acinput()

hat_n=[0]*3


res=1
for i in range(0,N):
    #print(res)
    #print(hat_n)
    k=0
    nzero=0

    hat_same=999999999
    for t,h in enumerate(hat_n):
        if h==A[i]:
            k+=1
            hat_same=t
        if h==0:
            nzero+=1
            pos_z=t
    
    if A[i]==0:
        if nzero==0:
            res=False
            break
        res*=nzero
        hat_n[pos_z]=1
        continue

    
    if k==0:
        res=False
        break
    
    res*=k
    res=res%1000000007
    hat_n[hat_same]+=1



print(res%1000000007)

Submission status: Wrong Answer

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N=int(input())
A=acinput()

hat_n=[0]*3


res=1
for i in range(0,N):
    print(res)
    print(hat_n)
    k=0
    nzero=0

    hat_same=999999999
    for t,h in enumerate(hat_n):
        if h==A[i]:
            k+=1
            hat_same=t
        if h==0:
            nzero+=1
            pos_z=t
    
    if A[i]==0:
        if nzero==0:
            res=False
            break
        res*=nzero
        hat_n[pos_z]=1
        continue

    
    if k==0:
        res=False
        break
    
    res*=k
    res=res%1000000007
    hat_n[hat_same]+=1

Submission status: Wrong Answer

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N=int(input())
A=acinput()

hat_n=[0]*3

hat_n[0]=0
res=1
for i in range(0,N):

    

    k=0
    nzero=0

    hat_same=-1
    for t,h in enumerate(hat_n):
        if h==A[i]:
            k+=1
            hat_same=t
        if h==0:
            nzero+=1
            pos_z=t
    
    if A[i]==0:
        if nzero==0:
            res=False
            break
        res*=nzero
        hat_n[pos_z]=1
        continue

    
    if k==0:
        res=False
        break
    
    res*=k
    hat_n[hat_same]+=1



print(res%1000000007)

Submission status: Wrong Answer

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

N = 100000
A = [x // 3 for x in range(100000)]

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    _ = int(input())
    A = [int(i) for i in input().split()]
    rgb = [0, 0, 0]
    ans = modint(1)
    for a in A:
        if rgb[0] == a:
            if rgb[0] == rgb[1] and rgb[0] == rgb[2]:
                ans *= 3
            elif rgb[0] == rgb[1]:
                ans *= 2
            rgb[0] += 1
        elif rgb[1] == a:
            if rgb[1] == rgb[2]:
                ans *= 2
            rgb[1] += 1
        elif rgb[2] == a:
            rgb[2] += 1
    print(ans if ans != 1 else 0)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
mod = 1000000007

b_list = [3] * 100000

ans = 1
for i in range(n):
  a = a_list[i]
  if a == 0:
    ans *= b_list[0]
  else:
    if  b_list[a] == 2  and b_list[a-1]  ==  1:
      ans *= 1
    else:
      ans *= min(b_list[a], (3 - b_list[a-1]))
  b_list[a] -= 1
  ans = ans % mod
print(ans%mod)