I am trying to solve the RIVALS problem on SPOJ: Starting from (0, 0), how many paths are there to reach point (X, Y), only taking one-unit steps moving to the right or up?  Constraints: 0X106, 0Y106, answer is to be given modulo (109+7).I am facing a performance issue with accessing elements of a list. I am also facing a runtime error if I am trying to access the list element.In order to get the nth element I am using [1,1,1,2]!!n, but I have been told that this runs in O(n) which is very slow.  Is there any other data structure in Haskell which gives O(1) access time for nth element?About my algorithm: the number of way to move form (0,0) to (x,y) in 2D plain and answer is:$$\frac{(x+y)!}{x!\ y!}$${-# LANGUAGE BangPatterns #-}{-# OPTIONS_GHC -O2 #-}import Data.Listimport Data.Bitsimport Data.Maybeimport Control.Monadimport qualified Data.ByteString.Char8 as CseqI :: Integer -> IntegerseqI x = seq x xseqB :: Bool -> BoolseqB x = seq x xmodExp' :: Integer -> Integer -> Integer -> Integer -> IntegermodExp' r b p m = let nextR = seqI $ (seqI $ r*b)`rem` m                      nextB = seqI $ (seqI $ b*b)`rem` m                      nextP = seqI $ shiftR  p 1                      incl  = seqB $ testBit p 0                      cont  = seqB $ nextP  /= 0                  in  if incl                         then if cont                                 then modExp' nextR nextB nextP m                                 else nextR                         else if cont                                 then modExp' r     nextB nextP m                                 else rmodExp :: Integer -> Integer -> Integer -> IntegermodExp b p m = modExp' 1 b p mreadInts :: IO [Int]readInts = fmap (map read.words) getLineread2Ints :: IO [Int]read2Ints = do     ints <- readInts     if length ints == 2 then return ints else do         putStrLn (sorry, could you give me exactly two integers,                   ++ separated by spaces?)         read2Intsp = 1000000007::Integerip = 1000000005::Integermtimes a b =  (a * b)`rem`pfacts = scanl mtimes 1 [1..2000001]anstable ::[Integer]anstable  =  factssolve ::Int->Int-> Integersolve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007main :: IO ()main = do    n <- readLn    forM_ [1..n::Int] (\i -> do       xs <- read2Ints       print $(solve (head xs) (last xs)))
Accessing list elements when counting the number of rectilinear paths
performance;programming challenge;haskell;combinatorics