mod = 10**9 + 7 N = int(input()) A = [int(input()) for _ in range(N)] from collections import defaultdict # Count the occurrences of each disliked number cnt = defaultdict(int) for a in A: cnt[a] += 1 # List of unique disliked numbers that appear at least once vals = list(cnt.keys()) # Precompute factorial modulo mod fact = [1] * (N + 1) for i in range(1, N + 1): fact[i] = fact[i - 1] * i % mod # Initialize DP: dp[k] is the number of ways to choose k distinct values dp = [0] * (N + 1) dp[0] = 1 for v in vals: c = cnt[v] # Update dp in reverse to avoid overwriting values we still need to process for j in range(N, -1, -1): if dp[j] and j < N: dp[j + 1] = (dp[j + 1] + dp[j] * c) % mod # Calculate the result using inclusion-exclusion principle result = 0 for k in range(0, N + 1): if dp[k] == 0: continue remaining = N - k if remaining < 0: continue # Current term: (-1)^k * dp[k] * (remaining)! term = dp[k] * fact[remaining] % mod if k % 2 == 1: term = (mod - term) % mod # Convert to positive mod value result = (result + term) % mod print(result)