main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  print $ fib n m
fastDoubling :: Int -> Int -> (Int, Int)
fastDoubling 0 mo = (0, 1)
fastDoubling 1 mo = (1, 1)
fastDoubling i mo
  = let (a, b) = fastDoubling (i `quot` 2) mo
    in if even i
       then (a * (2 * b `mod` mo - a + mo) `mod` mo, (a * a `mod` mo + b * b `mod` mo) `mod` mo)
       else ((a * a `mod` mo + b * b `mod` mo) `mod` mo, b * (2 * a `mod` mo + b) `mod` mo)

fib :: Int -> Int -> Int
fib i mo = case fastDoubling (i - 1) mo of
          (a, _) -> a `mod` mo