
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 b m1 p1 p2 =
  if x = m1 then
    not b && x <> p1
  else
    not (x = p1 && x = p2)
;;

let rec ans index b m1 p1 p2 k' =
  if table.(index) <> 0 then
    ans (index+1) (m1 = table.(index)) table.(index) p2 table.(index+3) k'
  else if k' = n - k - 1 then
    let aux x =
      if is_valid x b m1 p1 p2 then
        1
      else
        0
    in
    aux 1 + aux 2 + aux 3
  else
    if b then
      if p1 = m1 then
        2 * ans (index+2) false p1 table.(index+3) table.(index+4) (k'+1) mod 10000
      else if p1 <> 0 && p1 = p2 then
        ans (index+3) true p2 table.(index+4) table.(index+5) (k'+1)
      else if p1 <> 0 && p2 <> 0 then
        2 * ans (index+3) false p2 table.(index+4) table.(index+5) (k'+1) mod 10000
      else
        let x1 = m1 mod 3 + 1 in
        let aux x = ans (index+1) false x p2 table.(index+3) (k'+1) in
        (aux x1 + aux (x1 mod 3 + 1)) mod 10000
    else
      if m1 = p1 && m1 <> 0 then
        2 * ans (index+2) false p1 table.(index+3) table.(index+4) (k'+1) mod 10000
      else if p1 <> 0 && p1 = p2 then
        2 * ans (index+3) true p1 table.(index+4) table.(index+5) (k'+1) mod 10000
      else if p1 <> 0 && p2 <> 0 then
        3 * ans (index+3) false p2 table.(index+4) table.(index+5) (k'+1) mod 10000
      else
        let aux x = ans (index+1) (x = m1) x p2 table.(index+3) (k'+1) in
        ((aux 1 + aux 2) mod 10000 + aux 3) mod 10000
;;

ans 2 false table.(1) table.(3) table.(4) 0 |> string_of_int |> print_string
;;
p
