
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 memo = Hashtbl.create 10000
;;

let rec ans index b m1 p1 p2 k' =
  let key = (index, b, m1, p1, p2) in
  let f x = Hashtbl.add memo key x; x in
  if Hashtbl.mem memo key then
    Hashtbl.find memo key
  else
    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
      f (aux 1 + aux 2 + aux 3)
    else
      if b then
        if p1 = m1 then
          f (2 * ans (index+2) false p1 table.(index+3) table.(index+4) (k'+1) mod 10000)
        else if p1 <> 0 && p1 = p2 then
          f (ans (index+3) true p2 table.(index+4) table.(index+5) (k'+1))
        else if p1 <> 0 && p2 <> 0 then
          f (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
          f ((aux x1 + aux (x1 mod 3 + 1)) mod 10000)
      else
        if m1 = p1 && m1 <> 0 then
          f (2 * ans (index+2) false p1 table.(index+3) table.(index+4) (k'+1) mod 10000)
        else if p1 <> 0 && p1 = p2 then
          f (2 * ans (index+3) true p1 table.(index+4) table.(index+5) (k'+1) mod 10000)
        else if p1 <> 0 && p2 <> 0 then
          f (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
          f (((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
;;
print_string "\n";;

