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:
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 __name__ == '__main__':
    main()

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 = [-1, -1, -1]
    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] = a
        elif rgb[1] < a:
            if rgb[1] == rgb[2]:
                ans *= 2
            rgb[1] = a
        elif rgb[2] < a:
            rgb[2] = a
    print(ans)


if __name__ == '__main__':
    main()

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 = [-1, -1, -1]
    ans = modint(1)
    for a in A:
        if rgb[0] < a:
            if all(x >= 0 for x in rgb) and rgb[0] == rgb[1] and rgb[0] == rgb[2]:
                ans *= 3
            elif all(x >= 0 for x in rgb[:2]) and rgb[0] == rgb[1]:
                ans *= 2
            rgb[0] = a
        elif rgb[1] < a:
            if all(x >= 0 for x in rgb) and rgb[1] == rgb[2]:
                ans *= 2
            rgb[1] = a
            if a == 0:
                ans *= 2
        elif rgb[2] < a:
            rgb[2] = a
    print(ans*3)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
N = int(input())
A = [int(i) for i in input().split()]
count = [0]*N
dp = [0]*N
dp[0] = 3
count[0] += 1
for i, a in enumerate(A[1:]):
    if a == 0:
        dp[i+1] = dp[i]*(3-count[a])
    elif count[a] >= count[a-1]:
        print(0)
        exit()
    else:
        dp[i+1] = dp[i]*(count[a-1]-count[a])
    count[a] += 1
    dp[i+1] %= MOD
print(dp[-1])

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
        elif num_list[i] == 2:
            num_list[i] = 3
        else:
            print(0)
            exit()
    else:
        if num_list[i-1] == 0:
            print(0)
            exit()
        elif 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
        elif num_list[i] == 2:
            num_list[i] = 3
        else:
            print(0)
            exit()

print(pattern)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
X=[-1,-1,-1]
ans=1
mod=10**9+7
for i in range(N):
    tmp=0
    if A[i]>i:
        ans=0
    for j in range(3):
        if X[j]==A[i]-1:
            tmp+=1
    for j in range(3):
        if X[j]==A[i]-1:
            ans=tmp*ans
            ans%=mod
            X[j]+=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
X=[-1,-1,-1]
ans=1
mod=10**9+7
for i in range(N):
    tmp=0
    for j in range(3):
        if X[j]==A[i]-1:
            tmp+=1
    for j in range(3):
        if X[j]==A[i]-1:
            ans=tmp*ans
            ans%=mod
            X[j]+=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
_,a=open(0)
c=1
d=[3]+[0]*10**6
for a in map(int,a.split()):
  c=c*d[a]%(10**9+7)
  d[a]-=1
  d[a]+=1
print(c)

Submission status: Wrong Answer

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

XYZ = np.array([[0] * 3 for _ in range(N+1)])

for i in range(N):
    if XYZ[i][0] == A[i]:
        XYZ[i+1] = XYZ[i] + np.array([1, 0, 0])
    elif XYZ[i][1] == A[i]:
        XYZ[i+1] = XYZ[i] + np.array([0, 1, 0])
    else:
        XYZ[i+1] = XYZ[i] + np.array([0, 0, 1])

T = [sum(XYZ[i] == A[i]) for i in range(N)]
ans = 1
for t in T:
    ans *= (t % mod)
else:
    ans %= mod
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def main():
    mod = 1000000007
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [[0, 0, 0] for i in range(N+1)]
    ans = 1
    for i in range(N-1):
        a = A[i]
        ans = ans * cnt[i].count(a) % mod
        for j in range(3):
            cnt[i+1][j] = cnt[i][j]
        for j in range(3):
            if cnt[i][j] == a:
                cnt[i+1][j] = a+1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

arr = [0,0,0]
ans = 1
MOD = 1000000007

for i in range(len(List)):
  a = List[i]
  
  b = arr.count(a)
  
  if b > 0:
    j = arr.index(a)
    arr[j] = a + 1
    
    ans = ans * b
    
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

lst = list(map(int,input().split()))
mod = 1000000007
occur = [0]*(n+1)
count = 1
for i in range(n):
    if lst[i] != 0:
        count = count * occur[lst[i]-1] % mod
        occur[lst[i]-1] -= 1
    occur[lst[i]] += 1

if occur[0] == 1:
    count = count*3 % mod
else:
    count = count*6 % mod

print(count)

Submission status: Wrong Answer

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

arr = [0,0,0]
ans = 1

for i in range(len(List)):
  a = List[i]
  
  b = arr.count(a)
  
  if b > 0:
    j = arr.index(a)
    arr[j] = a + 1
    
    ans = ans * b
    
print(ans)

Submission status: Wrong Answer

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

arr = [0,0,0]
ans = 1

for i in range(len(List)):
  a = List[i]
  
  b = arr.count(a)
  
  if b > 0:
    j = arr.index(a)
    arr[j] = a + 1
    
    ans = ans * b
    print(b)
    
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

    t = [[0,0,0]]

    total = 1
    for i in range(n):
        count = 0
        for j in range(3):
            if t[i][j] == a[i]:
                count +=1
        for j in range(3):
            if t[i][j] == a[i]:
                tmp = deepcopy(t[i])
                tmp[j] += 1
                t.append(tmp)
                break
        
        if count == 0:
            return 0
        total *= count
    return total

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