import Data.List main = readLn >>= print . solve solve :: Int -> Int solve n = fst . foldl' f (0, n) $ [1..n] where f :: (Int, Int) -> Int -> (Int, Int) f (s, c) i = ((s + c * (modpow i (n - i))) `mod` modulus, c `modmul` (n - i) `moddiv` (i + 1)) modulus :: Int modulus = 10^9 + 7 modmul :: Int -> Int -> Int modmul a b = (a * b) `mod` modulus moddiv :: Int -> Int -> Int moddiv a b = modmul a (modpow b $ modulus - 2) modpow :: Int -> Int -> Int modpow a b | b == 0 = 1 | even b = modpow (modmul a a) (b `div` 2) | otherwise = modmul a $ modpow a (b - 1)