{-# LANGUAGE BangPatterns #-}

import Data.Bits
import Data.List
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Data.Coerce

primes :: [Int]
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

-- given (p:prime) (n:nat), returns maximal e with p^e | n! 
exponentInFactorial :: Int -> Int -> Int
exponentInFactorial p = loop 0
  where
    loop !acc n | n < p = acc
    loop !acc n = loop (acc + n') n'
      where n' = n `div` p

query :: Int -> Int
query n =
  x74
  + x24 * (x2-1)
  + x14 * (x4-1)
  + ((x4 * (x4-1)) `div` 2) * (x2-2)
  where
    expts = (`exponentInFactorial` n) <$> primes
    x74 = length $ filter (>= 74) expts
    x24 = length $ filter (>= 24) expts
    x14 = length $ filter (>= 14) expts
    x4 = length $ filter (>= 4) expts
    x2 = length $ filter (>= 2) expts