output_description: Print the number of possible combinations of colors of the N people's hats,
  modulo 1000000007.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 A_3 ... A_N
attempt: MOD = 10**9 + 7
  
  
  class ModInt:
      def __init__(self, x):
          self.x = x % MOD
  
      def __str__(self):
          return str(self.x)
  
      __repr__ = __str__
  
      def __add__(self, other):
          return (
              ModInt(self.x + other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x + other)
          )
  
      def __sub__(self, other):
          return (
              ModInt(self.x - other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x - other)
          )
  
      def __mul__(self, other):
          return (
              ModInt(self.x * other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x * other)
          )
  
      def __truediv__(self, other):
          return (
              ModInt(self.x * pow(other.x, MOD - 2, MOD))
              if isinstance(other, ModInt)
              else ModInt(self.x * pow(other, MOD - 2, MOD))
          )
  
      def __pow__(self, other):
          return (
              ModInt(pow(self.x, other.x, MOD))
              if isinstance(other, ModInt)
              else ModInt(pow(self.x, other, MOD))
          )
  
      __radd__ = __add__
  
      def __rsub__(self, other):
          return (
              ModInt(other.x - self.x)
              if isinstance(other, ModInt)
              else ModInt(other - self.x)
          )
  
      __rmul__ = __mul__
  
      def __rtruediv__(self, other):
          return (
              ModInt(other.x * pow(self.x, MOD - 2, MOD))
              if isinstance(other, ModInt)
              else ModInt(other * pow(self.x, MOD - 2, MOD))
          )
  
      def __rpow__(self, other):
          return (
              ModInt(pow(other.x, self.x, MOD))
              if isinstance(other, ModInt)
              else ModInt(pow(other, self.x, MOD))
          )
  
  
  def cmb(fact, n, r):
      return fact[n] / fact[n - r] / fact[r]
  
  
  def solve(N, A):
      ret = ModInt(0)
      group = [[] for _ in range(3)]
      for idx, a in enumerate(A):
          if not a:
              for idx, g in enumerate(group):
                  if not g:
                      group[idx].append(0)
                      break
          for idx, g in enumerate(group):
              if g and g[-1] == a - 1:
                  group[idx].append(a)
                  break
  
      fact = [ModInt(1)]
      for i in range(1, N + 1):
          fact.append(fact[i - 1] * i)
  
      rest = N
      pattern = 0
      for g in group:
          if not g:
              break
          ret += cmb(fact, rest, g[-1] + 1)
          rest -= g[-1] + 1
          pattern += 1
  
      return ret * cmb(fact, 3, pattern)
  
  
  if __name__ == "__main__":
      N = int(input())
      A = list(map(int, input().split()))
      print(solve(N, A))
  
problem_description: 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.
samples: [{"input": "6\n    0 1 2 3 4 5", "output": "3\n    \n\nWe have three possible combinations, as follows:\n\n  * Red, Red, Red, Red, Red, Red\n  * Blue, Blue, Blue, Blue, Blue, Blue\n  * Green, Green, Green, Green, Green, Green\n\n* * *"}, {"input": "3\n    0 0 0", "output": "6\n    \n\n* * *"}, {"input": "54\n    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", "output": "115295190"}]