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: def read():
      N = int(input().strip())
      A = list(map(int, input().strip().split()))
      return N, A
  
  
  def next_state(c, a, n_patterns):
      # c := c[0] >= c[1] >= c[2]
      idx = c.index(a)
      n_equals = 1
      n_equals += 1 if c[idx % 3] == c[(idx + 1) % 3] else 0
      n_equals += 1 if c[idx % 3] == c[(idx + 2) % 3] else 0
      c[idx % 3] += 1
      n_patterns *= n_equals
      n_patterns %= 1000000007
      return c, n_patterns
  
  
  def solve(N, A):
      c = [0, 0, 0]
      n = 1
      for a in A:
          c, n = next_state(c, a, n)
      return n
  
  
  if __name__ == "__main__":
      inputs = read()
      output = solve(*inputs)
      print("%d" % output)
  
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"}]