n = int(input()) A = [int(input()) for _ in range(n)] MOD = 10**9 + 7 cnt = [0] * 5000 # Since A_i <= 4999 for a in A: cnt[a] += 1 # Collect all values v where cnt[v] > 0 vs = [v for v in range(5000) if cnt[v] > 0] # Precompute factorials modulo MOD fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i-1] * i % MOD # Initialize dynamic programming array dp = [0] * (n + 1) dp[0] = 1 # Process each value v with cnt[v] > 0 for v in vs: current_cnt = cnt[v] for k in range(n - 1, -1, -1): if dp[k]: dp[k+1] = (dp[k+1] + dp[k] * current_cnt) % MOD ans = 0 for k in range(n + 1): ways = dp[k] * fact[n - k] % MOD if k % 2 == 1: ways = (-ways) % MOD ans = (ans + ways) % MOD print(ans % MOD)