30pts Haskell 有无优化空间

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies, BangPatterns #-}
import qualified Data.ByteString.Char8 as C
import Control.Applicative
import Data.Array
import Data.Bits

int :: C.ByteString -> Int
int s = let Just (n, _) = C.readInt s in n

readInt :: IO Int
readInt = int <$> C.getLine

integer :: C.ByteString -> Integer
integer s = let Just (n, _) = C.readInteger s in n 
 
readIntegers :: IO [Integer]
readIntegers = map integer . C.words <$> C.getLine

replicateTransitionM :: Monad m => Int -> a -> (a -> m a) -> m a
replicateTransitionM 0 x _ = return x
replicateTransitionM n x f = f x >>= \y -> replicateTransitionM (n - 1) y f

replicateTransitionM_ :: Monad m => Int -> a -> (a -> m a) -> m ()
replicateTransitionM_ n x f = replicateTransitionM n x f >> return ()

-- Z3 a = {alpha, beta, gamma, p}
data Z3 a = MatrixSimplified a a a a

infixl 5 >*< 
(>*<) :: (Integral a) => Z3 a -> Z3 a -> Z3 a
f0@(MatrixSimplified alpha0 beta0 gamma0 p0) >*< f1@(MatrixSimplified alpha1 beta1 gamma1 p1) 
  | p0 /= p1 = error "Failed to calculate the product of Z3's with different modules"
  | otherwise = MatrixSimplified alpha beta gamma p
  where 
    alpha = mod (alpha0 * alpha1) p0
    beta' = (mod (beta0 * alpha1) p0) + (mod (gamma0 * beta1) p0)
    beta = if beta' >= p0 then beta' - p0 else beta'
    gamma = mod (gamma0 * gamma1) p0
    p = p0

infixl 5 >!<
(>!<) :: (Integral a) => Z3 a -> Int -> a
f0@(MatrixSimplified alpha beta gamma p) >!< t
  | t == 0 = alpha
  | t == 1 = beta
  | t == 2 = gamma
  | otherwise = error "Failed to fetch an element of Z3"

calcExp :: (Integral a) => Z3 a -> Z3 a -> Integer -> a
calcExp f0 f1 t = (calcExp' f0 f1 t) >!< 1
  where
    calcExp' _ f1 0 = f1
    calcExp' f0 f1 t
      | even t = calcExp' (f0 >*< f0) f1 (shiftR t 1)
      | otherwise = calcExp' (f0 >*< f0) (f1 >*< f0) (shiftR t 1)

main :: IO ()
main = do
  t <- readInt
  replicateTransitionM_ t 0 $ \x -> do
    [n, a, b, p] <- readIntegers
    let [f0, f1] = [MatrixSimplified a (toInteger 1) b p, MatrixSimplified (toInteger 0) (toInteger 1) b p]
    (putStrLn $ show (calcExp f0 f1 n)) >> (return 0)
  return ()