program colorful_hats_2
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer :: n, a(100000) = 0, i, c(3) = 0, j
  integer(8) :: ans = 1_8, m
  read(*,*) n
  read(*,*) a(1:n)
  do i = 1, n
    m = 0_8
    do j = 1, 3
      if (a(i) == c(j)) m = m+1_8
    end do
    ans = mod(ans*m,md)
    do j = 1, 3
      if (a(i) == c(j)) then
        c(j) = c(j)+1
        exit
      end if
    end do
  end do
  write(*,'(i0)') ans
end program colorful_hats_2