CF938E Max History

You are given an array $ a $ of length $ n $ . We define $ f_{a} $ the following way: - Initially $ f_{a}=0 $ , $ M=1 $ ; - for every $ 2

The first line contains integer $ n $ ( $ 1

Print the only integer, the sum of $ f_{a} $ over all $ n! $ permutations of the array $ a $ modulo $ 10^{9}+7 $ .

For the second example all the permutations are: - $ p=[1,2,3] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[1,3,2] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[2,1,3] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[2,3,1] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[3,1,2] $ : $ f_{a} $ is equal to $ 0 $ ; - $ p=[3,2,1] $ : $ f_{a} $ is equal to $ 0 $ . Where $ p $ is the array of the indices of initial array $ a $ . The sum of $ f_{a} $ is equal to $ 4 $ .