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: p = 1000000007
  N = int(input())
  A = [int(i) for i in input().split()]
  
  n = A.count(0)
  
  
  Num = [0] * N
  lis = [[0]]
  ma = -1
  for i in A:
      if ma + 1 == i:
          lis.append([0])
          ma += 1
      else:
          lis[i + 1].append(0)
      for j in range(len(lis[i])):
          lis[i][j] += 1
  lis.pop(0)
  n = len(lis[0])
  if n == 3:
      ans = 6
  else:
      ans = 3
  for li in lis:
      if 0 in li:
          li.remove(0)
          for i in range(len(li)):
              li[i] -= 1
  
      if 1 in li:
          li.remove(1)
          for i in range(len(li)):
              li[i] -= 1
      if len(li) == 2:
          if li[0] == li[1] == 2:
              ans = (ans * 2) % p
      if len(li) == 3:
          if li == [3, 3, 3]:
              ans = (ans * 6) % p
          elif li == [3, 3, 2]:
              ans = (ans * 4) % p
          elif li == [3, 2, 2]:
              ans = (ans * 2) % p
  print(ans)
  
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"}]