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

    dp = [defaultdict(lambda:0) for _ in range(N+1)]
    dp[0][(0,0,0)] = 1
    for i in range(N):
        a = A[i]
        k = i + 1
        for key in dp[k-1].keys():
            for ii, v in enumerate(key):
                if v == a:
                    tmp = list(key)
                    tmp[ii] += 1
                    dp[k][tuple(tmp)] += dp[k-1][key] % mod
    ans = 0
    for key in dp[N].keys():
        ans = (ans + dp[N][key]) % mod
    #print(dp)
    print(ans)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,A=ilint()
C=counter()
C.add(-1,3)
ans=1
for a in A:
    C.add(a)
    if a-1 not in C or C[a]>3:
        ans=0
        break
    ans*=C[a-1]-C[a]+1
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int) 
N = int(input()); MOD = pow(10,9)+7
A = list(map(int,input().split()))
#for x in A:
#  dic[x] += 1
ans = 1
for x in A:
  if x == 0:
    if dic[x] == 0:
      ans *= 3%MOD
    elif dic[x] == 1:
      ans *= 2%MOD
    elif dic[x] == 2:
      ans *= 1%MOD
    else:
      print(0);exit()
  else:
    if dic[x-1]-dic[x] == 0:
      print(0);exit()
    elif dic[x-1]-dic[x] == 1:
      ans *= 1
    elif dic[x-1]-dic[x] == 2:
      ans *= 2%MOD
    elif dic[x-1]-dic[x] == 3:
      ans *= 3%MOD
  dic[x] += 1
print(ans%MOD)

Submission status: Accepted

Solution code:
N=int(input())
A=map(int, input().split())
P=1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N + 1)]

for a in A:
  ans=ans*cnt[a]%P
  if ans==0:
    break
  cnt[a]-=1
  cnt[a+1]+=1

print(ans)

Submission status: Accepted

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

MOD = 10**9+7

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

rgb = [0, 0, 0]

ans = 1
for i in range(n):
    ans *= rgb.count(a[i])
    ans %= MOD
    # print(rgb, a[i], ans)
    for j in range(3):
        if rgb[j] == a[i]:
            rgb[j] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    MOD = 10**9 + 7
    cnt = 1
    x, y, z = 0, 0, 0
    for a in A:
        tmp = 0
        is_used = False  # x,y,zのどこかに配った。
        if a == x:
            tmp += 1
            if not is_used:
                x += 1
                is_used = True
        if a == y:
            tmp += 1
            if not is_used:
                y += 1
                is_used = True
        if a == z:
            tmp += 1
            if not is_used:
                z += 1
                is_used = True
        cnt *= tmp
        cnt = cnt % MOD
    print(cnt)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    colors = [0] * 3
    ans = 1

    for i in range(N):
        count = 0
        for k in range(3):
            if colors[k] == targets[i]:
                if count == 0:
                    colors[k] += 1
                count += 1
        ans *= count
        ans %= MOD

    print(ans)


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
x,y,z = 0,0,0
ans = 1
mod = 10**9+7
for i in range(N):
    c = [x,y,z].count(A[i])
    if c == 0:
        print(0)
        exit(0)
    ans = ans*c % mod
    if x == A[i]:
        x += 1
    elif y == A[i]:
        y += 1
    else:
        z += 1
    l = list(sorted([x,y,z]))
    x,y,z = l[0],l[1],l[2]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

l=[0,0,0]

mod=10**9+7

ans=1
for i in a:
  ans*=l.count(i)
  ans%=mod
  for j in range(3):
    if l[j]==i:
      l[j]+=1
      break

print(ans)

Submission status: Accepted

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

l=[0,0,0]

mod=10**9+7

ans=1
for i in a:
  l_cnt=l.count(i)
  ans*=l_cnt
  ans%=mod
  for j in range(3):
    if l[j]==i:
      l[j]+=1
      break

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

l=[0,0,0]

mod=10**9+7

ans=1
for i in a:
  l_cnt=l.count(i)
  ans*=l_cnt
  ans%=mod
  for j in range(3):
    if l[j]==i:
      l[j]+=1
      break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

A=list(map(int, input().split()))
p=10**9+7
if A[0]!=0:
    print(0)
    exit()

dp=[0]*N
dp[0]=3
counts=[0]*N #前が何人か(自分が＊人目)
counts[0]=1
for i in range(1,N):
    a=A[i]
    if a==0:
        dp[i]=(dp[i-1]*(3 - counts[a]))%p
    else:
        dp[i]=(dp[i-1]*(counts[a-1] - counts[a]))%p
    

    counts[a]+=1

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

mod = 10**9 + 7
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

ans = 1
xyz = [0] * 3
for i in range(N):
    tmp = 0
    index = -1
    for j in range(3):
        if A[i] == xyz[j]:
            tmp += 1
            if index == -1:
                index = j

    xyz[index] += 1
    ans *= tmp
    ans %= mod

    # print(xyz)
    # print(ans)

print(ans)

Submission status: Accepted

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

hat = [0,0,0]

mod = 10**9 + 7

ans=1

for i in range(n):
    tmp=0
    index=0
    for j,k in enumerate(hat):
        if k==a[i]:
            tmp+=1
            index=j

    ans = (ans*tmp)%mod

    hat[index]+=1

print(ans)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
mita = [0] * -~n
mita[-1] = 3
mod = 10 ** 9 + 7
c = 1
for i in range(n):
    c = c * (mita[a[i] - 1] - mita[a[i]]) % mod
    mita[a[i]] += 1
print(c)

Submission status: Accepted

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

MOD = 10**9 + 7

dp = [0] * (n + 1)
dp[0] = 3
ans = 1
for x in arr:
    ans *= dp[x]
    dp[x] -= 1
    dp[x + 1] += 1
    ans %= MOD

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
dp = [[-1,-1,-1,1] for _ in range(N+1)]
for i in range(N):
    check = dp[i][:3]
    pattern = check.count(a[i]-1)
    dp[i+1][3] *= dp[i][3]*pattern
    dp[i+1][3] = dp[i+1][3]%1000000007
    for k in range(3):
        dp[i+1][k]= dp[i][k]
    if dp[i][0]== a[i]-1:
        dp[i+1][0] = a[i]
    elif dp[i][1] ==a[i]-1:
        dp[i+1][1] = a[i]
    elif dp[i][2] ==a[i]-1:
        dp[i+1][2] = a[i]
print(dp[N][3])

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
cnt = [0, 0, 0]
ans = 1
for a in A:
    possible = sum(c == a for c in cnt)
    ans *= possible
    ans %= MOD
    for i in range(3):
        if cnt[i] == a:
            cnt[i] += 1
            break
print(ans)

Submission status: Accepted

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

unused = [3] * N
ans = 1
for i in range(N):
    if A[i] == 0:
        ans *= unused[0]
        unused[0] -= 1
    else:
        ans *= unused[A[i]] - unused[A[i]-1]
        unused[A[i]] -= 1
    ans %= mod
        
print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

count = defaultdict(int)
count[0] = 3

ans = 1
for i in range(N):
  ans *= count[A[i]]
  ans %= mod
  count[A[i]] -= 1
  count[A[i]+1] += 1
  
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n = read_int()
    a = read_int_list()
    ans = 1
    cnt = [3] + [0] * n
    for x in a:
        ans = ans * cnt[x] % MOD
        cnt[x] -= 1
        cnt[x + 1] += 1
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    d = defaultdict(int)
    ans = 1
    d[-1] = 3
    for a in A:
        ans *= (d[a - 1] - d[a])
        ans %= 1000000007
        d[a] += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10**9+7

A = [a+1 for a in A]
C = [0]*(n+1)
C[0] = 3
ans = 1
for a in A:
    if C[a-1] < C[a]:
        print(0)
        exit()
    else:
        ans *= C[a-1]-C[a]
        ans %= mod
        C[a] += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
MOD = 1000000007

ct = [0, 0, 0]
ans = 1
for a in A:
    cta = ct.count(a)
    if cta:
        ct[ct.index(a)] += 1
        ans = (ans * cta) % MOD
    else:
        print(0)
        exit()
print(ans)

Submission status: Accepted

Solution code:
M =  10**9 + 7 
n = int(input())
a = [int(i) for i in input().split()]  #; print(a)

counter = [0] * (n+1) ; counter[0] = 3
ans = 1
for i in range(n):
    ans *=  counter[a[i] - 1 +1] - counter[a[i] +1]
    ans = ans % M
    counter[a[i] +1] += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a_=max(a)
con=[0]*(a_+1)
tou=[0]*(a_+1)
ans=[]
for i in range(len(a)):
    u=a[i]
    if u==0:
        con[0]+=1
        tou[0]+=1
        ans.append(4-con[0])

    else:
        con[u]+=1 
        tou[u]+=1  
        ans.append(tou[u-1]-con[u]+1)
c=1
for i in range(len(ans)):
    c*=ans[i]
    c=c%(10**9+7)
print(c%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a_=max(a)
con=[0]*(a_+1)
tou=[0]*(a_+1)
ans=[]
for i in range(len(a)):
    u=a[i]
    if u==0:
        con[0]+=1
        tou[0]+=1
        ans.append(4-con[0])

    else:
        con[u]+=1 
        tou[u]+=1  
        ans.append(min(tou[u-1]-con[u]+1,4-con[u]))
c=1
for i in range(len(ans)):
    c*=ans[i]
    c=c%(10**9+7)
print(c%(10**9+7))

Submission status: Accepted

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

kMod = 10**9+7

mem = [0, 0, 0]
cnt = 1

for a in A:
   if a not in mem:
       cnt = 0
       break
   cnt *= mem.count(a)
   cnt %= kMod
   mem[mem.index(a)] = a+1
print(cnt)

Submission status: Accepted

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

dp=[1]
col=[]
for i in range(N):
    if A[i]==0:
        col.append(1)
        dp.append(dp[-1]*(4-len(col)))
    else:
        p=0
        for c in range(len(col)):
            if col[c]==A[i]:
                p+=1
                if p==1:
                    col[c]+=1
        dp.append(dp[-1]*p%mod)

print(dp[-1]%mod)

Submission status: Accepted

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

cnt=[0,0,0]
ans=1
mod=10**9+7

for aa in a:
    tmp=0
    for c in cnt:
        if aa==c:
            tmp+=1
    
    if tmp>0:
        for i in range(3):
            if cnt[i]==aa:
                cnt[i]+=1
                break
    
    ans*=tmp
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
# なんか雑に書いたらサンプル3通ったしこれでよさそう
# なんかしらんけど2ケースでWAなる
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1
d = [0] * (n + 10)
d[0] = 3
for i in range(n):
    ans *= d[a[i]]
    d[a[i]] -= 1
    d[a[i] + 1] += 1
    ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

cnt = [0]*n
ans = 1

for i in a:
    if i>0: ans *= max(0,cnt[i-1] - cnt[i])
    cnt[i] += 1
    if cnt[i]>3:ans = 0
    ans %= mod

ans *= 3 if cnt[0]==1 else 6

print(ans%mod)

Submission status: Accepted

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

mod = 10**9+7
ans = 1
hat = [0, 0, 0]

for i in range(n):
  count = hat.count(q[i])
  ans *= count
  ans %= mod
  if ans == 0:
    break
  for j in range(3):
    if hat[j] == q[i]:
      hat[j] += 1
      break
      
print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_ls = list(map(int, input().split()))
hat_nperson = [0,0,1]
ans = 3
mod = 10**9+7

if a_ls[0] != 0 or (n != 1 and a_ls[1] == 2):
    print(0)
    sys.exit()

for i in range(1,n):
    n_same = a_ls[i]
    n_choices = 0
    choice_ind = -1
    for j,person in enumerate(hat_nperson):
        if person == n_same:
            n_choices += 1
            choice_ind = j
    if choice_ind == -1:
        print(0)
        sys.exit()
    hat_nperson[choice_ind] += 1
    ans *= n_choices
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()
mod = 10**9+7

ans = 1
x,y,z = -1,-1,-1
for i in range(N):
    a = A[i]
    k = [x,y,z].count(a-1)
    if k == 3:
        ans *= 3
        ans %= mod
        z += 1
    elif k == 2:
        ans *= 2
        ans %= mod
        if x == a-1:
            x = a
        elif y == a-1:
            y = a
        else:
            z = a
    elif k == 1:
        if x == a-1:
            x = a
        elif y == a-1:
            y = a
        else:
            z = a
    else:
        print(0)
        exit()

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

p = 10 ** 9 + 7
n = int(input())
a = [int(x) for x in input().split()]

num = defaultdict(int)
num[-1] = 3
col = [None] * n
for i in range(n):
    col[i] = num[a[i] - 1]
    num[a[i]] += 1
    num[a[i] - 1] -= 1

ans = 1
for i in range(n):
    ans = ans * col[i] % p

print(ans)

Submission status: Accepted

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

ans = 1
for i, a in enumerate(A):
    f = True
    count = 0
    for j in range(3):
        sums[i + 1][j] = sums[i][j]
        if sums[i][j] == a:
            count += 1
            if f:
                sums[i + 1][j] += 1
                f = False
    ans = ans * count % MOD
#print(sums)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()
ans = 1
cnt = [0] * (n+1)
for i in range(n):
    if a[i] == 0:
        ans *= 3 - cnt[0]
        ans %= mod
    else:
        ans *= cnt[a[i]-1] - cnt[a[i]]
        ans %= mod
    cnt[a[i]] += 1
print(ans)

Submission status: Accepted

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

ans, cnt = 1, [0, 0, 0]
for i in a:
    ans = ans * cnt.count(i) % mod
    for j in range(3):
        if cnt[j] == i:
            cnt[j] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e

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

counts = [0, 0, 0]
result = 1
for i in range(n):
    a = A[i]
    # print(a, counts, result)
    cnt = counts.count(a)
    result *= cnt
    result %= MOD
    for j in range(len(counts)):
        if counts[j] == a:
            counts[j] += 1
            break

print(result)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():

    inf = 10 ** 18
    mod = 10 ** 9 + 7

    n = ir()
    a = lr()
    dp = [[0, 0, 0] for i in range(n+1)]
    for i in range(n):
        now = a[i]
        if dp[i][0] == now:
            dp[i+1][0] = dp[i][0]+1
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
        elif dp[i][1] == now:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]+1
            dp[i+1][2] = dp[i][2]
        elif dp[i][2] == now:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]+1
        else:
            print(0)
            sys.exit()

    ans = 1
    for i in range(n):
        x,y,z = dp[i]
        now = a[i]
        if x == now and y == now and z == now:
            ans *= 3
        elif (x == now == y) or (y == now == z) or (z == now == x):
            ans *= 2
        ans %= mod
    print(ans)




    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
counter=[0 for i in range(n+1)]
counter[0]=3
ans=1
for i in range(n):
    ans=(ans*(counter[lis[i]]-counter[lis[i]+1]))%mod
    counter[lis[i]+1]+=1
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter as cc
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    mod = 10**9 + 7
    n = ii()
    a = li()
    t = [0]*(n)
    ans = 1
    for i in range(n):
        if a[i] == 0:
            tmp = 3
        else:
            tmp = t[a[i]-1]
        ans *= tmp-t[a[i]]
        ans %= mod
        t[a[i]] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
color1 = -1
color2 = -1
color3 = -1
 
m = 10**9+7
patern = 1
 
for a in A:
    if color1 == a-1 and color2 == a-1 and color3 == a-1:
        patern = (patern * 3)%m
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 == a-1):
        patern = (patern * 2)%m
        color2 = a
 
    elif (color1 == a-1 and color2 == a-1 and color3 != a-1):
        patern = (patern * 2)%m
        color1 = a
    elif (color1 == a-1 and color2 != a-1 and color3 != a-1):
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 != a-1):
        color2 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 == a-1):
        color3 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 != a-1):
        patern = 0
        break
print(patern)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
mem = [0, 0, 0]
ans = 1
for i in range(n):
    ans *= mem.count(A[i])
    ans %= mod
    if ans == 0: break
    idx = mem.index(A[i])
    mem[idx] += 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*N
    ans = 3
    for a in A:
        if a == 0:
            if B[a] == 1:
                ans *= 2
        else:
            ans *= B[a-1] - B[a]
        B[a] += 1
        if 3 < B[a] or (a != 0 and B[a-1] < B[a]):
            ans = 0
            break
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N = int(input())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ctr = [0, 0, 0]
ans = 1
for a in X:
    ptn = sum(a == v for v in ctr)
    ans = ans * ptn % MOD

    if ans == 0:
        break

    for i in range(3):
        if ctr[i] == a:
            ctr[i] += 1
            break

print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    N = read_int()
    A = read_ints()
    T = [0, 0, 0]
    answer = 1
    modulo = 1000000007
    for a in A:
        if a not in T:
            return 0
        answer = (answer*T.count(a))%modulo
        T[T.index(a)] += 1
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys

n=int(input())
A=list(map(int,input().split()))
p=10**9+7

status=[1,0,0]
ans=3

if A[0]!=0:
    print(0)
    sys.exit()

for i in range(1,n):
    count=status.count(A[i])
    if count==0:
        print(0)
        sys.exit()
    
    ans=(ans*count)%p
    status[status.index(A[i])]+=1

print(ans)

Submission status: Accepted

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