Evaluating Fibonacci-sequence-based recurrence relation (SPOJ Flibonakki)
First of all, make sure to add type signatures and use the appropriate number type. All your numbers are fine with Int, since they're bounded by

2 * (1000000006 * 1000000006)


Therefore, you can get rid of Integer throughout your program and simply use Int:

fib2 :: Int -&gt; (Int, Int)
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
 | even n    = ((a*a + b*b)`rem` 1000000007, (c*c - a*a)`rem` 1000000007)
 | otherwise = ((c*c - a*a)`rem` 1000000007, (b*b + c*c)`rem` 1000000007)
 where (a,b) = fib2 (n `quot` 2 - 1)
       c     = a + b


Next, you want to use rem and quot, since they're usually faster and provide the same result as mod and div on positive numbers.

We also add a type signature to solve:

solve :: Int -&gt; Int
solve n = (a*b)`rem`1000000007
    where (a,b) = fib2((2*n-1)`rem`2000000016)


Last but not least, we now simplify your main:

main :: IO ()
main = C.getContents &gt;&gt;= putStrLn . unlines . map (show.solve. fst . fromJust . C.readInt) . tail . C.words


However, I don't think that the IO part is the bottle-neck, so your usual String methods should be fine for this challenge, e.g.

main = getContents &gt;&gt;= putStrLn . unlines . map (show . solve . read) . tail . words


Indeed, this version of your program gets accepted of SPOJ. But so did your one. I guess that they updated the GHC version* and used the appropriate optimization flags. But you can make sure that they use optimization via

{-# OPTIONS_GHC -O2 #-}


* I just rememered that there was a defect with even in GHC 7.10. If they used GHC 7.10 (which is unlikely), then you were affected by that defect.