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())
a = list(map(int,input().split()))
mod = 10**9 + 7
dp = [0 for i in range(n+1)]
dp[0] = 3
r,g,b = 1,0,0
for i in range(1,n):
    if a[i] == r:
        if r == g and g == b:
            dp[i] = dp[i-1]*3
        elif r == g or r == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        r += 1
    elif a[i] == g:
        if g == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        g += 1
    elif a[i] == b:
        dp[i] = dp[i-1]
        b += 1
    else:
        dp[i] = 0
print(dp[n-1])

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
    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())
it=list(map(int,input().split()))
mod=1000000007
dp=[[0,0,0] for i in range(n+1)]
dp[-1]=[1,1,1]
col=[0 for i in range(n)]
fe=[]
cu=0
tot=1
ss={}

for i in range(n):
    try:
        x=ss[it[i]-1]
        tot*=len(x)
        tot%=mod
        no=ss[it[i]-1].pop()
        col[i]=col[no]
        try:
            ss[it[i]].add(i)
        except:
            ss[it[i]]=set([i])
        
    except:
        col[i]=cu
        cu+=1
        try:
            ss[it[i]].add(i)
        except:
            ss[it[i]]=set([i])
        
        
                
if cu==3:
    tot*=6
elif cu==2:
    tot*=6
else:
    tot*=3
print(tot%mod)

Submission status: Wrong Answer

Solution code:
def examE(mod):
    N = I()
    A = LI()
    a =[0,0,0]
    cur = 1
    for i in A:
        if a[0]==i:
            if a[0]==a[1]:
                if a[1]==a[2]:
                    cur *= 3
                else:
                    cur *=2
            a[0]+=1
        elif a[1]==i:
            if a[1] == a[2]:
                cur *= 2
            a[1] +=1
        elif a[2]==i:
            a[2]+=1
        else:
            print("err")
        a.sort(reverse=True)
        cur %=mod
    print(cur)
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=[3]+[0]*n
m=10**9+7
c=1
for i in a:
    s[i+1]+=1
    c=(c*s[i])%m
    s[i]-=1
    if s[i]<0:
        print(0)
        break
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
dp = [0 for i in range(n+1)]
dp[0] = 3
r,g,b = 1,0,0
for i in range(1,n):
    if a[i] == r:
        if r == g and g == b:
            dp[i] = dp[i-1]*3
            dp[i] %= mod
            r += 1
        elif r == g or r == b:
            dp[i] = dp[i-1]*2
            dp[i] %= mod
            r += 1
        else:
            dp[i] = dp[i-1]
            r += 1
    elif a[i] == g:
        if g == b:
            dp[i] = dp[i-1]*2
            dp[i] %= mod
            g += 1
        else:
            dp[i] = dp[i-1]
            g += 1
    else:
        dp[i] = dp[i-1]
        b += 1
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n=inp()
    a=inpl()
    ans=3
    num=[1,0,0]
    for i in range(1,n):
        cnt=0
        index=0
        for j in range(3):
            if num[j]==a[i]:
                cnt+=1
                index=j
        if cnt==1:
            num[index]+=1
        elif cnt==2:
            num[index]+=1
            ans=(ans*2)%mod
        elif cnt==3:
            num[index]+=1
            ans=(ans*3)%mod
        else:
            print(0)
            return
    print(ans%mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
r = 0
g = 0
b = 0

cnt = 1

for i in range(N):
    if A[i] == r:
        if r == g and r == b:
            cnt *= 3
        elif r == g or r == b:
            cnt *= 2
        r += 1
    elif A[i] == g:
        if g == b:
            cnt *= 2
        g += 1
    else:
        b += 1
    cnt %= mod
    
print(cnt)

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 a[i]==red:
        red+=1
    elif a[i]==gre:
        gre+=1
    elif a[i]==blu:
        blu+=1
    ans*=temp
    ans=ans%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * N
dp[0] = 1
r = 1
g = 0
b = 0
for i in range(N - 1):
  f = 0
  if a[i + 1] == r:
    dp[i + 1] += dp[i]
    f = 0
  if a[i + 1] == g:
    dp[i + 1] += dp[i]
    f = 1
  if a[i + 1] == b:
    dp[i + 1] += dp[i]
    f = 2
  if f == 0: r += 1
  if f == 1: g += 1
  if f == 2: b += 1
  dp[i + 1] %= mod
print((3 * dp[-1]) % mod)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

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

res = 1
values = [0, 0, 0]

for e in a:
    yo = 0
    for v in values:
        if v == e:
            yo += 1
    if yo > 1:
        res = (res * yo) % MOD

    for i in range(3):
        if values[i] == e:
            values[i] += 1
            break

print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 1000000007
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n=inp()
    a=inpl()
    ans=3
    num=[1,0,0]
    for i in range(1,n):
        cnt=0
        index=0
        for j in range(3):
            if num[j]==a[i]:
                cnt+=1
                index=j
        if cnt==1:
            num[index]+=1
        elif cnt==2:
            num[index]+=1
            ans=(ans*2)%mod
        else:
            num[index]+=1
            ans=(ans*3)%mod
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations, permutations

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]

    mod = 1000000007
    rgb = [0, 0, 0]
    count = 1
    for i in range(N):
        a = A[i]
        if rgb[0] == a:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 3
                    count %= mod
                else:
                    count *= 2
                    count %= mod
            rgb[0] += 1
        else:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 2
                    count %= mod
                rgb[1] += 1
            else:
                rgb[2] += 1
    
    print(count)
                    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = []
MOD = 10 ** 9 + 7
for i in range(n):
    b = a[i]
    c = a[:i]
    if b == 0:
        v = 3
    else:
        v = c.count(b - 1)
    v -= c.count(b)
    l.append(v)

# l = l[::-1]
res = 1
for i in l:
    if i == 0:
        continue
    res *= i
# print(l)
print(res % MOD)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
MOD = 1000000007

def calc(A):
    CA = Counter(A)
    if max(CA.values()) > 3:
        return 0
    
    pop = [0]*(N+3)
    pop[-1] = 3
    
    res = 1
    for a in A:
        if pop[a-1] <= 0:
            return 0
        pop[a-1] -= 1
        pop[a] += 1
        res = (res*pop[a]) %MOD
    
    if pop[-1]:
        res = res*3%MOD
        
    return res
        

print(calc(A))

Submission status: Wrong Answer

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

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

col = [1,0,0]

ans = 3
cnt = 2

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

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N = int(input())

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

lis = [0,0,0]
ans = 1

for i in range(N):

    na = A[i]
    ind = 0
    nn = 0

    for j in range(3):
        if lis[j] == na:
            nn += 1
            ind = j

    lis[ind] += 1

    if nn == 2:
        ans *= 2
    elif nn == 3:
        ans *= 3

    ans %= mod
    #print (lis)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
c = np.array([0, 0, 0])
ans = 1
for i in A:
    ans *= sum(c == i)
    if i == c[0]:
        c[0] += 1
    elif i == c[1]:
        c[1] += 1
    else:
        c[2] += 1
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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:
    ans *= sum(np.array([high, mid, low]) == i)
    if i == high:
        high += 1
    elif i == mid:
        mid += 1
    else:
        low += 1
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[(i, ma, mi)] = 0
        return 0

    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[(i, ma, mi)] = 0
        return 0
    
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma < mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, r, b):
    if i == N:
        return 1
    if (i, r, b) in dp:
        return dp[(i, r, b)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == r:
        ans += f(i + 1, r + 1, b)
    if A[i] == b:
        ans += f(i + 1, r, b + 1)
    if A[i] == i - r - b:
        ans += f(i + 1, r, b)

    dp[(i, r, b)] = ans % mod
    return dp[(i, r, b)]

print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10 ** 15
MOD = 10 ** 9 + 7
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import pi
from functools import lru_cache

def main():
    n = int(input())
    num = list(map(int,input().split()))
    
    @lru_cache(maxsize = None)
    def dfs(a,b,c):
        if a + b + c == n:
            return 1
        ans = 0
        if num[a + b + c] == a:
            ans += dfs(a + 1,b,c)
            ans %= MOD
        if num[a + b + c] == b:
            ans += dfs(a,b + 1,c)
            ans %= MOD
        if num[a + b + c] == c:
            ans += dfs(a,b,c + 1)
            ans %= MOD
        return ans
    
    print(dfs(0,0,0))

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10 ** 15
MOD = 10 ** 9 + 7
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import pi
from functools import lru_cache

def main():
    n = int(input())
    num = list(map(int,input().split()))
    
    @lru_cache(maxsize = None)
    def dfs(i,a,b,c):
        if i == n:
            return 1
        ans = 0
        if num[i] == a:
            ans += dfs(i + 1,a + 1,b,c)
            ans %= MOD
        if num[i] == b:
            ans += dfs(i + 1,a,b + 1,c)
            ans %= MOD
        if num[i] == c:
            ans += dfs(i + 1,a,b,c + 1)
            ans %= MOD
        return ans
    
    print(dfs(0,0,0,0))

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

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
    if len(cur) > len(last):
        a = 0
        while True:
            a += 1 
    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:  # mistake why???
    #     break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
L=[]
mod = 1000000007
import collections
ans=1
for i in range(n):
  c=collections.Counter(L)
  c=c.most_common()
  
  if A[i]==0:
    if 0 in L:
      ans*=3-c[0][1]
    else:
      ans *=3
  else:
    if A[i] in L:
      if c[A[i]-1][1] - c[A[i]][1] <=0 :
        print(0)
        exit()
      else:
        ans = (ans*(c[A[i]-1][1] - c[A[i]][1]))%mod
    else:
      if A[i]-1 not in L:
        print(0)
        exit()
      else:
        ans = (ans*(c[A[i]-1][1]))%mod
  L.append(A[i])
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

MOD = 10**9 + 7

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

ptns = Counter([(0, 0, 0)])
#print('ptns:', ptns)
for A in As:
    ptn2s = Counter()
    for ptn, num in ptns.items():
        for i in range(3):
            if ptn[i] == A:
                ptn2 = list(ptn)
                ptn2[i] += 1
                ptn2s[tuple(ptn2)] += num
                ptn2s[tuple(ptn2)] %= MOD
    ptns = ptn2s

#print(ptns)
print(sum(ptns.values()) % MOD)

Submission status: Time Limit Exceeded

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%1000000007)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
mod = 1000000007
def main():
    N = I()
    L = LI()
    D = [0]*(N+2)
    D[0] = 3
    ans = 1
    
    for num in L:
        if D[num] == 0 or D[num+1] >= 3:
            print(0)
            sys.exit()
        temp = D[num] - D[num+1]
        D[num+1] += 1
        ans *= temp
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 1000000007

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

d = {-1:3}
ans = 1
for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    if a-1 not in d:
        print(0)
        exit()
    ans = ans*d[a-1]%mod
    d[a-1] -= 1

#print(d)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict
dic = defaultdict(int)
dic[0] = 3
ans = 1

mod = 1000000007
for a in A:
  ans *= dic[a]
  ans = ans % mod
  dic[a] -= 1
  dic[a+1] += 1
print(ans)

Submission status: Accepted

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

ans=1

d={}

ch=0

mod=10**9+7

for i in range(n):
  if a[i]==0:
    if 0 not in d:
      d[0]=1
      ans*=3
    else:
      if d[0]==1:
        d[0]=2
        ans*=2
      elif d[0]==2:
        d[0]=3
      else:
        ch+=1
        break
      
  else:
    if a[i] not in d:
      d[a[i]]=1
      if a[i]-1 not in d:
        ch+=1
        break
      else:
        ans*=d[a[i]-1]
    else:
      if d[a[i]]==1:
        d[a[i]]=2
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=2:
            ans*=d[a[i]-1]-1
          else:
            ch+=1
            break
      elif d[a[i]]==2:
        d[a[i]]=3
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=3:
            ans*=1
          else:
            ch+=1
            break
      else:
        ch+=1
        break
        
  ans=(ans%mod)
  
if ch==0:
  print(ans)
else:
  print(0)

Submission status: Accepted

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

ans = 1
l = [0] * N
for i in range(N):
  n = A[i]
  if 0 < n:
    ans *= l[n-1] - l[n]
  else:
    ans *= 3 - l[n]
  l[n] += 1
  ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
r,g,b=[-1],[-1],[-1]
ans=1
for i in range(n):
    f=1
    count=0
    if r[-1]==a[i]-1:
        count+=1
        r.append(a[i])
        f=0
    if g[-1]==a[i]-1:
        count+=1
        if f:
            g.append(a[i])
            f=0
    if b[-1]==a[i]-1:
        count+=1
        if f:
            b.append(a[i])
            f=0
    if f:
        print(0)
        exit()
    ans=(ans*count)%(10**9+7)
print(ans)

Submission status: Accepted

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

R, B, G = 0, 0, 0
ans = 1

for a in A:
    if R == a:
        if B == a and G == a:
            ans *= 3
        elif B == a or G == a:
            ans *= 2
        else:
            ans *= 1
        R += 1
    elif B == a:
        if G == a:
            ans *= 2
        else:
            ans *= 1
        B += 1
    elif G == a:
        ans *= 1
        G += 1
    else:
        print(0)
        exit()
    
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
c = [0 for i in range(n+1)]
c[0] = 3
ans = 1

for i in range(n):
  ans *= c[a[i]]
  ans %= mod
  c[a[i]] -= 1
  c[a[i]+1] += 1
print (ans)

Submission status: Accepted

Solution code:
P=10**9+7
N=int(input())
A=list(map(int, input().split()))
ans=1
c=[0,0,0]
for i in range(N):
  a,f,k=A[i],-1,0
  for j in range(3):
    if c[j]==a:
      k+=1
      if f==-1:
        c[j]+=1
        f=j
  ans=(ans*k)%P
print(ans)

Submission status: Accepted

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

m = 10**9+7
r, b, g = 0, 0, 0
ans = 1

for aa in a:
    if aa == r == b == g:
        ans *= 3
    elif aa == r == b or aa == b == g or aa == g == r:
        ans *= 2
    elif aa != r and aa != b and aa != g:
        print(0)
        exit()
    ans %= m

    aa += 1
    if aa > r:
        r = aa
    elif aa > b:
        b = aa
    elif aa > g:
        g = aa

print(ans%m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
G = [0]*3
ans = 1
for i in range(N):
    x = 0
    cnt = 0
    for j, g in enumerate(G):
        if g == A[i]:
            x = j if cnt == 0 else x
            cnt += 1
    
    G[x] += 1
    ans *= cnt
    ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    mod=1e9+7
    n=int(input())
    a=list(map(int,input().split()))
    ans=1
    cnt=[0]*(n+1)
    cnt[0]=3
    for i in range(n):
        if cnt[a[i]]>0:
            ans=(ans*cnt[a[i]])%mod
            cnt[a[i]]-=1
            cnt[a[i]+1]+=1
        else :
            ans=0
    print(int(ans))
resolve()

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
l=list(map(int,input().split()))
ans=1
rgb=[0,0,0]
for i in range(n):
    c=0
    for j in range(3):
        if l[i]==rgb[j]:
            c+=1
    if c==0:
        print(0)
        exit()
    p=rgb.index(l[i])
    if not 0<=p<=2:
        print(0)
        exit()
    rgb[p]+=1
    ans*=c
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    lst=list(map(int,input().split()))
    mod=10**9+7
    sm=1
    color=[0,0,0]
    for x in lst:
        if x not in color : sm=0;break
        sm*=color.count(x)
        sm%=mod
        color[color.index(x)]+=1
    print(sm)

main()

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
MOD = 10**9 + 7
ans = 1

lst = [0] * 3

for aa in a:
    cnt = 0
    j = -1
    for i, l in enumerate(lst):
        if l == aa:
            cnt += 1
            j = i
    if j == -1:
        ans = 0
        break
    ans *= cnt
    ans %= MOD
    lst[j] += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = None
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        if cache == None:
            print(0)
            return
        current[cache] += 1
        #print(current)
    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = 0
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        current[cache] += 1
        #print(current)
    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = 1
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        current[cache] += 1
        #print(current)
    print(ans)

if __name__ == "__main__":
    run()