import Data.Semigroup import Data.Monoid import qualified Control.Arrow as Arrow import qualified Data.Vector.Unboxed as VU import qualified Data.ByteString.Char8 as BSC8 -- https://blog.miz-ar.info/2019/01/fast-fibonacci/ data FibPair a = FibPair !a !a deriving (Eq, Show) instance (Num a) => Semigroup (FibPair a) where FibPair a b <> FibPair a' b' = FibPair (a * b' + (b - a) * a') (a * a' + b * b') stimes = stimesMonoid instance (Num a) => Monoid (FibPair a) where mempty = FibPair 0 1 fibOne :: (Num a) => FibPair a fibOne = FibPair 1 1 fibPair :: Int -> FibPair Integer fibPair i = stimesMonoid i fibOne fastDoubling :: Int -> Integer -> (Integer, Integer) 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 - a) `mod` mo, (a * a + b * b) `mod` mo) else ((a * a + b * b) `mod` mo, b * (2 * a + b) `mod` mo) fib :: Int -> Integer -> Integer fib i mo = case fastDoubling (i - 1) mo of (a, _) -> a main :: IO () main = do (n, mo) <- parse2 print $ fib n (fromIntegral mo) type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt parse2 :: IO (Int, Int) parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine