Your Haskell code builds a huge thunked accumulator value, so of course it's slow (put bang patterns on all arguments). Also, you should use rem instead of mod. Make those tiny changes and you'll get a 5x speedup, to half the performance of the C code.