MOD = 10**9 + 7 n = int(input()) A = [int(input()) for _ in range(n)] from collections import defaultdict cnt = defaultdict(int) for a in A: cnt[a] += 1 vals = list(cnt.values()) m = len(vals) max_k = min(m, n) # Initialize dp array for elementary symmetric sums dp = [0] * (max_k + 1) dp[0] = 1 for c in vals: for k in range(min(m, max_k), 0, -1): dp[k] = (dp[k] + dp[k-1] * c) % MOD # Precompute factorials modulo MOD fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i-1] * i % MOD result = 0 for k in range(0, max_k + 1): if k > n: continue ek = dp[k] sign = 1 if k % 2 == 0 else MOD - 1 term = (sign * ek) % MOD term = term * fact[n - k] % MOD result = (result + term) % MOD print(result % MOD)