import Control.Monad
import Control.Monad.ST (ST, runST)
import Data.Ratio
import Data.List
import qualified Data.Vector.Mutable as V

facs :: [Integer]
facs = 1 : zipWith (*) [1..] facs

tangent :: Int -> Integer
tangent m = runST $
  do v <- V.unsafeNew (n + 1)
     zipWithM_ (\x -> x `seq` V.unsafeWrite v x) [0..n] facs
     forM_ [1..n] $ \k ->
       do a0 <- V.unsafeRead v (k - 1)
          let go a j =
                do b <- V.unsafeRead v j
                   let c = fromIntegral (j - k) * a + fromIntegral (j - k + 2) * b
                   c `seq` V.unsafeWrite v j c
                   return c
          foldM_ go a0 [k..n]
     V.unsafeRead v n
  where n = fromIntegral m

bernoulli :: Integer -> Rational
bernoulli 0 = 1
bernoulli 1 = -0.5
bernoulli n | odd n = 0
bernoulli n = negateIfOdd (n `div` 2) $ (n * tangent (fromInteger $ n `div` 2 - 1)) % (2 ^ n - 4 ^ n)
  where negateIfOdd n = if even n then id else negate