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:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 1000000007
    set1 = set([])
    set2 = set([])
    set3 = set([])
    ans = 1
    for v in a:
        if v == 0:
            if 0 in set1:
                if 0 in set2:
                    set3.add(0)
                else:
                    set2.add(0)
                    ans = ans*2%mod
            else:
                set1.add(0)
                ans = ans*3%mod
        else:
            if v in set1:
                if v in set2:
                    set3.add(v)                
                else:
                    set2.add(v)
                    if v-1 in set2:
                        if v-1 in set3:
                            ans = ans*2%mod
            else:
                set1.add(v)
                if v-1 in set2:
                    if v-1 in set3:
                        ans = ans*3%mod
                    else:
                        ans = ans*2%mod
    print(ans%mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

mod = 10**9+7
ans = 1

num = [0]*(n+1)
num[0] = 3

if a[0] == 0:
    ans *= 3
    num[0] -= 1
    num[1] += 1
else:
    print(0)
    exit()

for i in range(1,n):
    if i < a[i]:
        print(0)
        exit()
    if i == a[i]:
        continue
    ans *= num[a[i]]
    ans %= mod
    num[a[i]] -= 1
    num[a[i]+1] += 1
        
    
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[0 for i in range(N)]
p=1
MOD=1000000007

for i in A:
    L[i]+=1
    if i==0:
        if L[0]==1:
            p*=3
        elif L[0]==2:
            p*=2
        else:
            p*=1
    else:
        if L[i]==1:
            p*=L[i-1]
        elif L[i]==2:
            p*=(L[i-1]-L[i]+1)
        else:
            p*=1
    p%=MOD

print(p%MOD)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
ans = 1
mod = 1000000007
cnt = 0
if A[0] != 0:
    print(0)
    sys.exit()
else:
    maxA = max(A)
    dp = [0] * (max(A) + 1)
    for i in A:
        if i == 0:
            dp[0] += 1
            cnt += 1
        else:
            if dp[i-1] <= 0:
                print(0)
                sys.exit()
            else:
                ans *= dp[i-1]
                ans %= 1000000007
                dp[i-1] -= 1
                dp[i] += 1
if cnt == 1:
    print((ans * 3)%1000000007)
elif cnt ==2:
    print((ans * 6)%1000000007)
else:
    print((ans * 6) % 1000000007)

Submission status: Wrong Answer

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

count = 1

unused = [0] * N
max = 0

for a in A_list:
	if a > 0:
		if unused[a - 1] == 0:
			count = 0
			break
		count = (count * unused[a - 1]) % 1000000007
		unused[a - 1] -= 1
	unused[a] += 1
	if a == 0:
		max += 1

if max == 0:
	print(0)
elif max == 1:
	print((count * 3) % 1000000007)
else:
	print((count * 6) % 1000000007)

Submission status: Wrong Answer

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

mod = 10**9+7
ans = 1

num = [0]*(n+1)
num[0] = 3

if a[0] == 0:
    ans *= 3
    num[0] -= 1
    num[1] += 1
else:
    print(0)
    exit()

for i in range(1,n):
    if i < a[i]:
        print(0)
        exit()
    if i == a[i]:
        continue
    ans *= num[a[i]]
    ans %= mod
    num[a[i]] -= 1
    num[a[i]+1] += 1
        
    
print(ans)

Submission status: Wrong Answer

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

count = 1

unused = [0] * N
max = 0

for a in A_list:
	if a > 0:
		if unused[a - 1] == 0:
			count = 0
			break
		count = (count * unused[a - 1]) % 1000000007
		unused[a - 1] -= 1
	unused[a] += 1
	if a == 0:
		max += 1

if max == 0:
	print(0)
elif max == 1:
	print(count * 3)
else:
	print(count * 6)

Submission status: Wrong Answer

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 3
    red = 1
    blue = 0
    green = 0

    for i in range(1, N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count

    print(ans % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
MOD = 1000000007
num = int(input())
says = list(map(int, input().split()))

ans = 0
colors = 0
sets = [0, 0, 0]
for i in range(num):
    if colors == 0:
        sets[0] += 1
        colors += 1
        ans = 3
    elif colors == 1:
        if says[i] == 0:
            sets[1] += 1
            colors += 1
            ans *= 2
        else:
            sets[0] += 1
    elif colors == 2:
        if says[i] == 0:
            sets[2] += 1
            colors += 1
        else:
            if sets[0] == says[i]:
                sets[0] += 1
                if sets[1] == says[i]:
                    ans *= 2
            elif sets[1] == says[i]:
                sets[1] += 1
            else:
                ans = 0
                break
    elif colors == 3:
        if sets[0] == says[i]:
            sets[0] += 1
            if sets[1] == says[i] and sets[2] == says[i]:
                ans *= 3
            elif sets[1] == says[i] or sets[2] == says[i]:
                ans *= 2
        elif sets[1] == says[i]:
            sets[1] += 1
            if sets[2] == says[i]:
                ans *= 2
        elif sets[2] == says[i]:
            sets[2] += 1
        else:
            ans = 0
            break
#print(sets)
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
div = 1000000007

r = 0
b = 0
g = 0
pat = 1
for i, a in enumerate(A):
    if i==0:
        pat *= 3
        r += 1

    elif i==N-1:
        break

    elif r==b and b==g:
        pat *= 3
        r += 1

    elif r>b and b==g:
        if a==r:
            r += 1
        else:
            pat *= 2
            b += 1

    elif r==b and b>g:
        if a==r:
            pat *= 2
            r += 1
        else:
            g += 1

    elif r>b and b>g:
        if a==r:
            r += 1
        elif a==b:
            b += 1
        else:
            g += 1

    
print(pat%div)

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 + 1:
        rr += 1
    elif bb == bb +1:
        bb += 1
    else:
        gg += 1
print(((combinations_count(N, rr+1)%(10**9+7))*(combinations_count(N-rr-1, bb+1)%(10**9+7))*(combinations_count(N-rr-bb-2, gg+1)%(10**9+7)%10**9+7)*3))

Submission status: Wrong Answer

Solution code:
N = int(input())
lst = list(map(lambda x: int(x),input().split()))
d = {"A":0,"B":0,"C":0}
ans = 3
flag=True
for i in range(N):
  if lst[i]==d["A"]:
    d["A"]+=1
    x = d["A"]==d["B"]+d["A"]==d["C"]+1
    ans *= x
    continue
  elif lst[i]==d["B"]:
    d["B"]+=1
    x = d["B"]==d["C"]+1
    ans *= x
    continue
  elif lst[i]==d["C"]:
    d["C"]+=1
    continue
  else:
    flag=False
    break
if flag:
  print(ans%10*9+7)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 1
r = 1
b = 0
g = 0
MOD = 1000000007
if N == 1 and A[0] != 0:
    print(0)
    exit()
for i in range(1,N):
    a = A[i]
    count = 0
    flag = 0
    if a == r:
        r += 1
        count += 1
        flag = 1
    if a == b:
        if flag == 1:
            count += 1
        else:
            b += 1
            count += 1
            flag = 1
    if a == g:
        if flag == 1:
            count += 1
        else:
            g += 1
            count += 1
            flag = 1
    if flag == 0:
        print(0)
        exit()
    ans *= count
    ans %= MOD
ans *= 3
ans %= MOD
print(ans)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
  if a[:i].count(a[i]) == 2:
    ans = ans*3%1000000007
  if a[:i].count(a[i]) == 1:
    ans = ans*2%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = int(input())
    aa = LI()
    cnt = [0] * 100005
    check = [0] * 100005
    zero = 0
    ans = 1
    for a in aa:
        if a == 0:
            zero += 1
        else:
            if cnt[a - 1] == 0:
                print(0)
                exit()
            ans *= cnt[a - 1]
            ans %= md
            cnt[a - 1] -= 1
        cnt[a] += 1
        check[a] += 1
        if check[a] > 3:
            print(0)
            exit()
    if zero == 3:
        ans *= 6
    else:
        ans *= 3
    print(ans % md)

main()

Submission status: Wrong Answer

Solution code:
mod=1000000007

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

ans=1
c1=c2=c3=0
for Ai in A:
    if c1==c2==c3==Ai:
        c1+=1
        ans=ans*3%mod
    elif c1==c2==Ai:
        c1+=1
        ans=ans*2%mod
    elif c1==c3==Ai:
        a1+=1
        ans=ans*2%mod
    elif c2==c3==Ai:
        c2+=1
        ans=ans*2%mod
    elif c1==Ai:
        c1+=1
    elif c2==Ai:
        c2+=1
    elif c3==Ai:
        c3+=1

print(ans%mod)

Submission status: Wrong Answer

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

count = 0
ans = (3 ** n) % (10**9 + 7)

for i in range(1,n):
    if A[i-1] <= A[i]:
        ans = (ans // 3) % (10**9 +7)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
ans = 1
mod = 1000000007
cnt = 0
if A[0] != 0:
    print(0)
    sys.exit()
else:
    maxA = max(A)
    dp = [0] * (max(A) + 1)
    for i in A:
        if i == 0:
            dp[0] += 1
            cnt += 1
        else:
            if dp[i-1] <= 0:
                print(0)
                sys.exit()
            else:
                ans *= dp[i-1]
                ans %= 1000000007
                dp[i-1] -= 1
                dp[i] += 1
if cnt == 1:
    print(ans * 3)
elif cnt ==2:
    print((ans * 6)%1000000007)
else:
    print((ans * 6) % 1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 3

red=1
gre=0
blu=0
for i in range(1,n):
    temp=0
    if a[i] == red:
        temp+=1
    if a[i] == gre:
        temp+=1        
    if a[i] == blu:
        temp+=1
    if temp!=0:
        ans*=temp
    
        ans=ans%mod
    if a[i]==red:
        red+=1
        continue
    if a[i]==gre:
        gre+=1
        continue
    if a[i]==blu:
        blu+=1
        continue
    
    
print(ans)

Submission status: Wrong Answer

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

dp = [(3, [1, 0, 0])]
for i in range(1, N):
    p = dp[i - 1][0]

    cc = 0
    sw = False
    cp = [dp[i - 1][1][0], dp[i - 1][1][1], dp[i - 1][1][2]]
    for c in range(3):
        if As[i] == dp[i - 1][1][c]:
            cc += 1
            if not sw:
                cp[c] += 1
                sw = True
    p = (p * cc)
    dp.append((p, cp))
print(dp[N - 1][0] % E)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
sosu = 10 ** 9 + 7
dp = [0 for i in range(N)]

ans = 3
dp[0] = 1
for i in range(1, N):
    if dp[A[i] - 1] - dp[A[i]] >= 0:
        ans *= (dp[A[i]-1] - dp[A[i]])
        ans = ans % sosu
    else:
        ans = 0
    dp[A[i]] += 1
print(ans)

Submission status: Wrong Answer

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

count = 1

unused = [0] * N
max = 0

for a in A_list:
	if a > 0:
		if unused[a - 1] == 0:
			count = 0
			break
		count = (count * unused[a - 1]) % 1000000007
		unused[a - 1] -= 1
	unused[a] += 1
	if unused[a] > max:
		max = unused[a]

if max == 0:
	print(0)
elif max == 1:
	print(count * 3)
else:
	print(count * 6)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 1000000007
    set1 = set([])
    set2 = set([])
    set3 = set([])
    ans = 1
    for v in a:
        if v == 0:
            if 0 in set1:
                if 0 in set2:
                    set3.add(0)
                else:
                    set2.add(0)
                    ans = ans*2%mod
            else:
                set1.add(0)
                ans = ans*3%mod
        else:
            if v in set1:
                if v in set2:
                    set3.add(v)                
                else:
                    set2.add(v)
                    if v-1 in set2:
                        if v-1 in set3:
                            ans = ans*2%mod
            else:
                set1.add(v)
                if v-1 in set2:
                    if v-1 in set3:
                        ans = ans*3%mod
                    else:
                        ans = ans*2%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
div = 1000000007

r = 0
b = 0
g = 0
pat = 1
for i, a in enumerate(A):
    if i==0:
        pat *= 3
        r += 1

    elif i==N-2:
        break

    elif r==b and b==g:
        pat *= 3
        r += 1

    elif r>b and b==g:
        if a==r:
            r += 1
        else:
            pat *= 2
            b += 1

    elif r==b and b>g:
        if a==r:
            pat *= 2
            r += 1
        else:
            g += 1

    elif r>b and b>g:
        if a==r:
            r += 1
        elif a==b:
            b += 1
        else:
            g += 1
    
print(pat%div)

Submission status: Wrong Answer

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

mod = 1000000007
n = [0 for i in range(100000)]
ans = 3
n[0] = 1
for i in range(1, N):
    a = A[i]
    if n[a] == 0:
        ans = ans * n[a-1] % mod
    elif n[a] == 1:
        if n[a-1] == 2:
            ans = ans % mod
        else:
            ans = ans * 2 % mod
        
    else:
        ans = ans % mod
    n[a]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
mod=1000000007

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

ans=1
c1=c2=c3=0
for Ai in A:
    if c1==c2==c3==Ai:
        c1+=1
        ans=ans*3%mod
    elif c1==c2==Ai:
        c1+=1
        ans=ans*2%mod
    elif c2==c3==Ai:
        c2+=1
        ans=ans*2%mod
    elif c1==Ai:
        c1+=1
    elif c2==Ai:
        c2+=1
    elif c3==Ai:
        c3+=1

print(ans%mod)

Submission status: Wrong Answer

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 1


    red = 1
    blue = 0
    green = 0

    for i in range(1, N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count


    if ans == 0:
        print(6)
        exit()
    print((ans * 3) % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a=list(map(int,input().split(' ')))
mod = 10**9+7
ans = 1
color=[1,0,0]
g = 0
for i in a[1:]:
    cnt = 0
    for n,j in enumerate(color):
        if i==0 and j ==0:
            color[n]+=1
            cnt = 1
            break
        elif i==j:
            cnt += 1
            if cnt == 1:
                color[n]+=1
    ans *= cnt
    ans %= mod
for i in color:
    if i >0:
        g += 1
if g ==1:
    print(ans*3%mod)
else:
    print(ans*6%mod)

Submission status: Wrong Answer

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

count = 1

unused = [0] * N
max = 0

for a in A_list:
	if a > 0:
		count = (count * unused[a - 1]) % 1000000007
		unused[a - 1] -= 1
	unused[a] += 1
	if unused[a] > max:
		max = unused[a]

if max == 0:
	print(0)
elif max == 1:
	print(count * 3)
else:
	print(count * 6)

Submission status: Wrong Answer

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def solve(A, N):
    MOD = 1000000007
    x = 0
    y = 0
    z = 0
    count = 1
    for i in range(N):
        if A[i] == x:
            if x == y and x == z:
                count = (count * 3) % MOD
            elif x == y:
                count = (count * 2) % MOD
            x += 1
        elif A[i] == y:
            if y == z:
                count = (count * 2) % MOD
            y += 1
        elif A[i] == z:
            z += 1
    return count

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty(N, i8)
    for i, c in enumerate(map(int, stdin.readline().split())):
        A[i] = c
    print(solve(A, N))

main2()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
sosu = 10 ** 9 + 7
dp = [0 for i in range(N)]

ans = 3
dp[0] = 1
for i in range(1, N):
    ans *= (dp[A[i]-1] - dp[A[i]])
    ans = ans % sosu
    dp[A[i]] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    n_list = list(map(int, input().split()))
    color = [0, 0, 0]

    pattern = 1

    for i in n_list:
        # print(i,color.count(i), pattern)
        if color.count(i) > 0:
            pattern *= color.count(i)
            color[color.index(i)] += 1

    print(pattern % 1000000007)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

num_list = [0] * n
pattern = 1
waru = 1000000007

for i in x:
    if i == 0:
        if num_list[i] == 0:
            pattern *= 3
            num_list[i] = 1
            pattern %= waru
        elif num_list[i] == 1:
            pattern *= 2
            num_list[i] = 2
            pattern %= waru
        else:
            num_list[i] = 3
    else:
        if num_list[i] == 0:
            pattern *= num_list[i-1]
            num_list[i] = 1
            pattern %= waru
        elif num_list[i] == 1:
            pattern *= (num_list[i-1]-1)
            num_list[i] = 2
            pattern %= waru
        else:
            num_list[i] = 3

print(pattern)

Submission status: Wrong Answer

Solution code:
_ = input()
nums = list(map(int, input().split(' ')))
nums.reverse()
counts = {str(i):nums.count(i) for i in range(max(nums)+1)}

combis = []
val = 1
for num in nums:
    c = counts[str(num)]
    try:
        b = counts[str(num+1)]
    except KeyError:
        b = 0
    combi = c - b
    combis.append(combi)
    val = val * combi
    counts[str(num)] -= 1
print(val % 1000000007)

Submission status: Wrong Answer

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 1


    red = 1
    blue = 0
    green = 0

    for i in range(1, N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count

    if A.count(0) == 2:
        print(6)
        exit()

    print((ans * 3) % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
MOD=1000000007
n=int(input())
a=list(map(int,input().split()))
counter=1
kaijo=[1]
if a==range(n):
	print(3)
elif a==[0,0,0]:
	print(6)
else:
	for i in range(1,len(a)):
		if a[i]==a[i-1]:
			counter+=1
		elif counter>1:
			kaijo.append(counter)
			counter=1
	ans=6
	for i in range(len(kaijo)):
		ans*=math.factorial(kaijo[i])%MOD
	print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
ans = 1
mod = 1000000007
cnt = 0
if A[0] != 0:
    print(0)
else:
    maxA = max(A)
    dp = [0] * (max(A) + 1)
    for i in A:
        if i == 0:
            dp[0] += 1
            cnt += 1
        else:
            if dp[i-1] <= 0:
                print(0)
                sys.exit()
            else:
                ans *= dp[i-1]
                ans %= 1000000007
                dp[i-1] -= 1
                dp[i] += 1
if cnt == 1:
    print(ans * 3)
elif cnt ==2:
    print((ans * 6)%1000000007)
else:
    print((ans * 6) % 1000000007)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())

visited = [False for i in range(n)]

lst = list(map(int,input().split()))

def runlist():
    c = -1
    for i in range(n):
        if not visited[i] and lst[i] == c+1:
            c+=1
            visited[i] = True
    return c

a = runlist()
b = runlist()
c = runlist()

ss = [a,b,c]
ss.sort()

print(ss)

mod = 1000000007

def poww(n, e):
    x = 1
    for i in range(e):
        x = x*n % mod
    return x

if ss[0] == ss[1] and ss[1] == -1:
    print(3)
elif ss[0] == -1:
    print(poww(2,ss[1])*6 % mod)
else:
    print(poww(3,ss[0])*poww(2,ss[1])*6 % mod)

Submission status: Wrong Answer

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

count_r = 0
count_g = 0
count_b = 0
ans = 1

for a in A:
    if a == count_r == count_g == count_b:
        ans *= 3
    elif a == count_r ==count_g or a == count_g == count_b or a == count_b == count_r:
        ans *= 2
    else:
        ans *= 1
    
    if a == count_r:
        count_r += 1
    elif a == count_g:
        count_g += 1
    else:
        count_b += 1

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
lst=[]
N=int(input())
h = map(int, input().split())
c=1
A=list(h)
B=len(A)
for i in range(B):
 if len(lst)<A[i]:
  c=0
  break
 elif len(lst)==A[i]:
  lst.append(1)
 else:
  lst[A[i]]+=1
  if lst[A[i]]==4:
   c=0
   break
 if A[i]==0:
  c*=1
 elif lst[A[i]-1]-lst[A[i]]+1<=0:
  if A[i]==1:
   c*=(4-lst[A[i]])
  else:
   c=0
   break
 else:
  c*=(lst[A[i]-1]-lst[A[i]]+1)
if lst==[]:
 c=0
elif lst[0]==1:
 c*=3
else:
 c*=6
print(c%1000000007)

Submission status: Wrong Answer

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 1


    red = 1
    blue = 0
    green = 0

    for i in range(1, N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count

    if A.count(0) == 1:
        print(3)
        exit()

    print((ans * 3) % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 1


    red = 1
    blue = 0
    green = 0

    for i in range(1, N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count

    if A.count(0) == 1:
        print(3)
        exit()
    elif A.count(0) == 2:
        print(6)
        exit()

    print((ans * 3) % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    z = a[i]
    if z == 0:
        num = 3
        for j in range(0,i):
            if z == a[j]:
              num -= 1
        ans *= num
    else:
        num = 0
        for j in range(0,i):
            if z-1 == a[j]:
                num += 1
            if z == a[j]:
                num -= 1
        ans *= num
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[0 for i in range(N+1)]
p=1
MOD=1000000007

for i in A:
    L[i]+=1
    if i==0:
        if L[0]==1:
            p*=3
        elif L[0]==2:
            p*=2
    else:
        if L[i]==1:
            p*=L[i-1]
        elif L[i]==2:
            p*=(L[i-1]-L[i]+1)
    p%=MOD

print(p)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    z = a[i]
    if z == 0:
        num = 3
        for j in range(0,i):
            if z == a[j]:
              num -= 1
        ans *= num
    else:
        num = 0
        for j in range(0,i):
            if z-1 == a[j]:
                num += 1
            if z == a[j]:
                num -= 1
        ans *= num
    print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 1
mod = 1000000007
cnt = 0
if A[0] != 0:
    print(0)
else:
    maxA = max(A)
    dp = [0] * (max(A) + 1)
    for i in A:
        if i == 0:
            dp[0] += 1
            cnt += 1
        else:
            ans *= dp[i-1]
            ans %= 1000000007
            dp[i-1] -= 1
            dp[i] += 1
if cnt == 1:
    print(ans * 3)
elif cnt ==2:
    print((ans * 6)%1000000007)
else:
    print((ans * 6) % 1000000007)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import bisect
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

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

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

    if n == 1:
        if a[0] == 0:
            print(3)
        else:
            print(0)
        exit()
    elif n == 2:
        if a[1] == 0:
            print(6)
        if a[1] == 1:
            print(3)
        else:
            print(0)
        exit()

    if a[1] == 0 and a[2] == 0:
        x = 1
        y = 1
        z = 1
        res = 1
    elif a[1] == 0 and a[2] == 1:
        x = 2
        y = 1
        z = 0
        res = 2
    elif a[1] == 1 and a[2] == 2:
        x = 3
        y = 0
        z = 0
        res = 1
    else:
        print(0)
        exit()

    MOD = 10**9+7

    for i in range(3, n):
        if a[i] == x and a[i] != y:
            x += 1
        elif a[i] == x and a[i] == y and a[i] != z:
            res = res*2 % MOD
            x += 1
        elif a[i] == x and a[i] == y and a[i] == z:
            res = res*3 % MOD
            x += 1
        elif a[i] == y and a[i] != z:
            y += 1
        elif a[i] == y and a[i] == z:
            res = res*2 % MOD
            y += 1
        elif a[i] == z:
            z += 1
        else:
            print(0)
            exit()

    if y == 0:
        res = res* 3 % MOD
    else:
        res = res* 6 % MOD
    print(res)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

colvals = [0]*100000
#0,1,2の色
dif_colors = [0]*3
patterns = []
num = 3
for i in range(N):
    if A[i] == 0:
        for j in range(3):
            if dif_colors[j] == A[i]:
                dif_colors[j] = 1
                patterns.append(num)
                num -= 1
                break
        continue
    cnt = 0
    tmp_color = -1
    for j in range(3):
        if dif_colors[j] == A[i]:
            cnt += 1
            tmp_color = j
    dif_colors[tmp_color] += 1
    patterns.append(cnt)

ans = 1
for pattern in patterns:
    ans *= pattern
    ans %= 1000000007

print(ans)

Submission status: Wrong Answer

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

dp = [(3, [1, 0, 0])]
for i in range(1, N):
    p = dp[i - 1][0]

    cc = 0
    sw = False
    cp = [dp[i - 1][1][0], dp[i - 1][1][1], dp[i - 1][1][2]]
    for c in range(3):
        if As[i] == dp[i - 1][1][c]:
            cc += 1
            if not sw:
                cp[c] += 1
                sw = True
    p = (p * cc) % E
    dp.append((p, cp))
print(dp[N - 1][0])

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
c = [0 for _ in range(10**6+1)]
c[0] = 1
r = 3

for i in range(1,n):
    k = c[s[i]-1]-c[max(0, s[i])]
    if k==0: k=3
    r *= k
    c[s[i]]+=1
print(r%1000000007)