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 Fp(int):
      def __new__(self, x=0):
          return super().__new__(self, x % MOD)
  
      def inv(self):
          return self.__class__(super().__pow__(MOD - 2, MOD))
  
      def __add__(self, value):
          return self.__class__(super().__add__(value))
  
      def __sub__(self, value):
          return self.__class__(super().__sub__(value))
  
      def __mul__(self, value):
          return self.__class__(super().__mul__(value))
  
      def __floordiv__(self, value):
          return self.__class__(self * self.__class__(value).inv())
  
      def __pow__(self, value):
          return self.__class__(super().__pow__(value % (MOD - 1), MOD))
  
      __radd__ = __add__
      __rmul__ = __mul__
  
      def __rsub__(self, value):
          return self.__class__(-super().__sub__(value))
  
      def __rfloordiv__(self, value):
          return self.__class__(self.inv() * value)
  
      def __iadd__(self, value):
          self = self + value
          return self
  
      def __isub__(self, value):
          self = self - value
          return self
  
      def __imul__(self, value):
          self = self * value
          return self
  
      def __ifloordiv__(self, value):
          self = self // value
          return self
  
      def __ipow__(self, value):
          self = self**value
          return self
  
      def __neg__(self):
          return self.__class__(super().__neg__())
  
  
  def main():
      N, *A = map(int, open(0).read().split())
      C = [0] * (N + 1)
      C[-1] = 3
      ans = Fp(1)
      for a in A:
          ans *= C[a - 1]
          C[a - 1] -= 1
          C[a] += 1
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
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"}]