Submission #18299760

---

Source Code Expand

{-# LANGUAGE BangPatterns #-}

import Data.List
import qualified Data.Vector.Unboxed as U
import Data.Vector.Unboxed ((!), Vector)

main = sol <$> get >>= print

get = map read . words <$> getLine

sol [n,m] = foldl' f (Modulo 0) [0..n]
  where
  f s k = s + comb n k*sign k*perm m k*perm (m-k) (n-k)*perm (m-k) (n-k)
  fac :: U.Vector Int
  fac = U.scanl' (((`mod` p) .) . (*)) 1 $ U.generate m succ
  perm :: Int -> Int -> Modulo
  perm n r = Modulo (fac!n)*inv (fac!(n-r))
  comb :: Int -> Int -> Modulo
  comb n r = perm n r*inv (fac!r)

inv :: Int -> Modulo
inv 1 = Modulo 1
inv k = pwr (Modulo k) (p-2)

sign :: Int -> Modulo
sign x = if odd x then Modulo (-1) else Modulo 1

newtype Modulo = Modulo {getInt :: Int} deriving (Eq)

p = 10^9+7 :: Int

instance Num Modulo where
  Modulo a+Modulo b = Modulo ((a+b) `mod` p)
  Modulo a-Modulo b = Modulo ((a-b) `mod` p)
  Modulo a*Modulo b = Modulo ((a*b) `mod` p)
  abs = undefined
  signum = undefined
  fromInteger i = Modulo (fromIntegral i `mod` p)

instance Show Modulo where
  show (Modulo i) = show i

pwr :: Modulo -> Int -> Modulo
pwr !a !n
  | n == 0    = 1
  | odd n     = a*r
  | otherwise = r
  where
  q = pwr a (n `div` 2)
  r = q*q

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result