import Data.List
import Data.Ratio
import Data.Function
import qualified Data.Sequence as Seq

bernoulli :: Integer -> Rational
-- using explicit formula
-- apply a little bit of dynamic programming for computing binomial coefficients by saving all factorials
-- use sequence instead of list for faster acces by index for stored factorials
bernoulli m = let facs = Seq.fromList( scanl (*) 1 [1..m]) in
  let  binomCoeff n k = (facs`Seq.index`(fromIntegral n)) `div`(facs`Seq.index`(fromIntegral k) * facs`Seq.index`(fromIntegral(n-k))) in
    sum [(if even v then 1 else -1) * (k `binomCoeff` v) * v^m % (succ k) | k <- [0..m], v <- [0..k]]
{-TTEW-}