import Data.List
import Data.Ratio

choose :: Integer -> Integer -> Integer
n `choose` k = product [n-k+1..n] `div` product [1..k]

bernoulli :: Integer -> Rational
bernoulli 0 = 1
bernoulli n = let bernoulli_help n k l1 l2 = case l1 of [] -> sum l2
                                                        (x:xs) -> bernoulli_help n (k+1) xs ( l2 ++ [choose n k % (k - n - 1) * x])
              in
              let bernoulli_help_help n k l1 | k == n = last l1
                                             | otherwise = bernoulli_help_help n (k+1) (l1 ++ [bernoulli_help (k+1) 0 l1 [] ])
              in bernoulli_help_help n 0 [1]