AtCoder #4: D - 表現の自由 ( Freedom of expression )

Hackageのライブラリと多倍長を使ってシンプルにしてみる。

import Control.Applicative
import Data.List
import Data.Numbers.Primes

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  let factors = group $ primeFactors $ abs n
      ans = product (map (h m . genericLength) factors) * 2 ^ (m - 1)
  print $ (ans :: Integer) `mod` 1000000007

h n r = comb (n + r - 1) r

comb _ 0 = 1
comb n m = comb (n-1) (m-1) * n `div` m