let m_1e9 = int_of_float 1e9 + 7
let ( *^ ) x y = ((x mod m_1e9) * (y mod m_1e9)) mod m_1e9
let split_string ?(pattern=" ") = Str.split @@ Str.regexp pattern

let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n
let a = read_line () |> split_string |> List.map int_of_string

let rec loop ans arr = function
  | [] -> Printf.printf "%d\n" @@ ans
  | x :: xs -> 
      let t = Array.fold_left (fun s i -> s + if i = x then 1 else 0) 0 arr in
      let i = if arr.(0) = x then 0 else if arr.(1) = x then 1 else 2 in
      arr.(i) <- arr.(i) + 1;
      loop (ans *^ t) arr xs

let () = loop 1 (Array.make 3 0) a