import Control.Monad
import Control.Applicative
import Data.List

main = do
	[n, k] <- map (read :: String -> Int) . words <$> getLine
	l <- map (map (read :: String -> Int) . words) <$> replicateM k getLine
	print $ solve n l

func :: Int -> [[Int]] -> [(Int, Int)]
func n [] = [(x, -1) | x <- [1..n]]
func n ([a, b]:c) = map (\(x, y) -> if x == a then (x, b) else (x, y)) $ func n c

foldw :: [Int] -> Int
foldw [] = 0
foldw a = foldl1 (+) a

solvew :: Int -> Int -> [Int] -> Int
solvew _ _ [] = 1
solvew a b (c:d)
	| a == b = (foldw [solvew x a d | x <- [1..3], x /= a, x == c || c == -1]) `mod` 10000
	| otherwise = (foldw [solvew x a d | x <- [1..3], x == c || c == -1]) `mod` 10000

solve :: Int -> [[Int]] -> Int
solve n l = solvew (-2) (-2) $ map (\(x, y) -> y) $ func n l