import Control.Monad.ST
import qualified Data.HashTable.ST.Basic as H

type HT s = H.HashTable s Int Int

fibCore :: Int -> Int -> HT s -> ST s Int
fibCore n base cache = do
  if (n == 1) || (n == 2)
    then return 1
    else do
      u <- fibCoreCached (n - 1) base cache
      v <- fibCoreCached (n - 2) base cache
      return (mod (u + v) base)

fibCoreCached :: Int -> Int -> HT s -> ST s Int
fibCoreCached n base cache = do
  x <- H.lookup cache n
  case x of
    Just t -> return t
    Nothing -> do
      r <- fibCore n base cache
      H.insert cache n r
      return r

fib :: Int -> Int -> Int
fib n base = runST $ do
  cache <- H.new
  fibCoreCached n base cache

main :: IO()
main = putStrLn (show (fib 10000000 999983))