
let (n,k) = Scanf.sscanf (read_line ()) "%d %d" (fun w h -> (w, h))
;;

let table = Array.make (n+4) 0
;;

let rec get_input () =
  let (a, b) = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> (a,b)) in
  table.(a+1) <- b;
  get_input ()
;;

try get_input ()
with End_of_file -> ()
;;

let is_valid x m1 m2 p1 p2 =
  if x = m1 then
    not (x = m2 || x = p1)
  else
    not (x = p1 && x = p2)
;;

let rec ans index m1 m2 p1 p2 k' =
  if table.(index) <> 0 then
    ans (index+1) table.(index) m1 p2 table.(index+3) k'
  else
    let aux x =
      if is_valid x m1 m2 p1 p2 then
        if k' = n - k - 1 then
          1
        else
          ans (index+1) x m1 p2 table.(index + 3) (k'+1)
      else
        0
    in
    ((aux 1 + aux 2) mod 10000 + aux 3) mod 10000
;;

ans 2 table.(1) table.(0) table.(3) table.(4) 0 |> string_of_int |> print_string
;;
print_string "\n";;

