{-# LANGUAGE BangPatterns #-}
data Matrix a = Matrix !a !a !a !a

matrixMul :: Num a => Matrix a -> Matrix a -> Matrix a
matrixMul (Matrix a b c d) (Matrix a' b' c' d')
    = Matrix (a * a' + b * c') (a * b' + b * d') (c * a' + d * c') (c * b' + d * d')

matrixPow :: Num a => Matrix a -> Integer -> Matrix a
matrixPow _ 0 = Matrix 1 0 0 1
matrixPow m i = loop m m (i - 1)
    where
        loop acc !_ 0 = acc
        loop acc m 1  = matrixMul acc m
        loop acc m i  = case i `quotRem` 2 of
                            (j, 0) -> loop acc (matrixMul m m) j
                            (j, _) -> loop (matrixMul acc m ) (matrixMul m m) j

fib :: Integer -> Integer
fib i = let Matrix a b c d = matrixPow (Matrix 0 1 1 1) (i - 1)
        in b

main :: IO ()
main = interact $ show . solve . map (read :: String -> Integer) . words

solve :: [Integer] -> Integer
solve [n, m] = ( fib n ) `mod` m