Lib.hs

module Main where

import Control.Applicative
import Control.Monad 
import Data.List (foldl')
import qualified Data.Sequence as Seq
import qualified Data.Vector (freeze)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM


--------------------------------------------------------------------------------
-- Queue Implementation

type Queue a = Seq.Seq a
  
emptyQueue = Seq.empty  

enqueue a queue = a Seq.<| queue

dequeue queue = 
  case Seq.viewl queue of
    Seq.EmptyL ->
      Nothing

    a Seq.:< queue1 ->
      Just (a, queue1)

nullQueue = Seq.null  

-------------------------------------------------------------------------------- 

-- permutations :: Int -> Int -> Int
-- permutations n k =
--   let
--     step acc i =
--       acc * (n - i)
--   in
--     foldl' step n [1..(k - 1)]

combinations n k =
  let
    diff =
      n - k

    nominator =
      product [succ (max diff k) .. n]

    denominator =
      product [1..(min diff k)]
  in
    nominator `div` denominator

main :: IO ()
main = do
  testCases <- readLn 
  replicateM_ testCases $ do
    (n:k:[]) <- map read . words <$> getLine
    print $ combinations n k `mod` ((10^8) + 1)