import System.IO
import Data.List

main = do
    putStrLn $ show $ length partial
    where
        partial = nub [ take y x | x <- full, y <- [ 1 .. 9 ] ]
        full = [ x | x <- permutations [ 1 .. 9 ], valid (head x) (tail x) ]


valid current [] = True
valid current (next:rest) =
    if next `elem` (neighbors !! (current - 1))
        then valid next rest
        else False


neighbors =
    [[2, 4, 5], [1, 3, 4, 5, 6], [2, 5, 6], [1, 2, 5, 7, 8], [1, 2, 3, 4, 6, 7, 8, 9], [2, 3, 5, 8, 9], [4, 5, 8], [4, 5, 6, 7, 9], [5, 6, 8]]