combmod.hs

import qualified Data.Vector.Unboxed           as U
import           Data.Vector.Unboxed            ( (!) )
import qualified Data.Vector.Unboxed.Mutable   as UM
import           Control.Monad.ST
import           Control.Monad

base = 10 ^ 9 + 7 :: Int
maxL = 3 * 10 ^ 5 :: Int

n *% m = (n * m) `mod` base
facs = U.scanl' (*%) 1 $ U.generate maxL (+ 1)

invs = U.create f
 where
  f :: ST s (UM.MVector s Int)
  f = do
    v <- UM.new maxL
    UM.write v 0 1
    UM.write v 1 1
    forM_ [2 .. UM.length v - 1] $ \i -> do
      let (q, r) = divMod base i
      vr <- UM.read v r
      UM.write v i (base - vr * q `mod` base)
    return v

facinvs = U.tail $ U.scanl' (*%) 1 invs

combmod n k
  | n < k
  = 0
  | n < 0 || k < 0
  = 0
  | otherwise
  = facs ! n * (facinvs ! k * facinvs ! (n - k) `mod` base) `mod` base