Accessing list elements when counting the number of rectilinear paths

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: 0 ≤ X ≤ 10⁶, 0 ≤ Y ≤ 10⁶, answer is to be given modulo (10⁹ + 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 n^th 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 n^th 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.List
import Data.Bits
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Char8 as C

seqI :: Integer -> Integer
seqI x = seq x x

seqB :: Bool -> Bool
seqB x = seq x x



modExp' :: Integer -> Integer -> Integer -> Integer -> Integer
modExp' 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 r

modExp :: Integer -> Integer -> Integer -> Integer
modExp b p m = modExp' 1 b p m

readInts :: IO [Int]
readInts = fmap (map read.words) getLine

read2Ints :: 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?")
         read2Ints

p = 1000000007::Integer
ip = 1000000005::Integer
mtimes a b =  (a * b)`rem`p
facts = scanl mtimes 1 [1..2000001]

anstable ::[Integer]
anstable  =  facts

solve ::Int->Int-> Integer
solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007


main :: IO ()
main = do
    n <- readLn
    forM_ [1..n::Int] (i -> do
       xs <- read2Ints
       print $(solve (head xs) (last xs)))

Code organization

The definitions of readInts and read2Ints disrupt the mathematical code. The I/O routines belong further down, just before main.

import Data.Maybe and import qualified Data.ByteString.Char8 as C appear to be superfluous.

Abstraction

It is not immediately obvious from reading

solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007

that it is calculating

$$left(begin{array}{c} x+y \ y end{array}right) = frac{(x + y)!}{x! y!}mod p$$

I would expect to see

solve x y = modCombination (x + y) y p

modCombination n r p =
  (factorial n) * (modInvFactorial r) * (modFactorial (n - r)) `rem` p'
  where …

In some ways, you come close, but anstable obscures your intention. Why not ansTable, with the customary capitalization so that it doesn’t look like an stable? Why did you rename it from fact in the first place, making it more confusing? Why is 1000000007 hard-coded at the end, when you could have used p?

What is ip? 1000000005 is a magic number that appears nowhere in the stated challenge. What about 2000001? Where did that limit come from?