using System.Diagnostics; using System; using System.Linq; using System.Numerics; using System.Collections; using System.Collections.Generic; using System.IO; using System.Text; using static Functions; static class Program { static public void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(); Console.Out.Flush(); } } public class Solver { public Solver() { Solve(); } void Solve() { ModInt.MOD = 1000000007; int n = ri; var f = new ModFact(n); var c = new int[n]; for (int i = 0; i < n; i++) { int a = ri; if (a < n) c[a]++; } var dp = new ModInt[n + 1]; dp[0] = 1; for (int i = 0; i < n; i++) for (int j = i; j >= 0; j--) dp[j + 1] += dp[j] * c[i]; ModInt ans = 0; for (int i = 0; i <= n; i++) { if (i % 2 == 0) ans += dp[i] * f.Fact(n - i); else ans -= dp[i] * f.Fact(n - i); } Write(ans); } const long INF = 1L << 60; int ri { get { return (int)sc.Integer(); } } long rl { get { return sc.Integer(); } } ulong rul { get { return sc.UInteger(); } } double rd { get { return sc.Double(); } } string rs { get { return sc.Scan(); } } string rline { get { return sc.Line(); } } public StreamScanner sc = new StreamScanner(Console.OpenStandardInput()); T[] RepArray(T t, int count) => Enumerable.Repeat(t, count).ToArray(); void WriteJoin(string s, IEnumerable t) { Console.WriteLine(string.Join(s, t)); } void WriteMat(T[,] a) { int sz1 = a.GetLength(0); int sz2 = a.GetLength(1); for (int i = 0; i < sz1; i++) { var s = new List(); for (int j = 0; j < sz2; j++) s.Add(a[i, j].ToString()); WriteJoin(" ", s); } } void WriteMax(params long[] x) => Console.WriteLine(x.Max()); void WriteMin(params long[] x) => Console.WriteLine(x.Min()); void Write(object t) => Console.WriteLine(t.ToString()); void Write(string str, object arg1) => Console.WriteLine(str, arg1); void Write(string str, object arg1, object arg2) => Console.WriteLine(str, arg1, arg2); void Write(string str, object arg1, object arg2, object arg3) => Console.WriteLine(str, arg1, arg2, arg3); void Write(string str, params object[] arg) => Console.WriteLine(str, arg); void WriteFlush(object t) { Console.WriteLine(t.ToString()); Console.Out.Flush(); } void WriteError(object t) { Console.Error.WriteLine(t.ToString()); } void YN(bool t) { Console.WriteLine(t ? "YES" : "NO"); } void Yn(bool t) { Console.WriteLine(t ? "Yes" : "No"); } void yn(bool t) { Console.WriteLine(t ? "yes" : "no"); } } public static class Functions { public static int Popcount(ulong x) { x = (x & 0x5555555555555555UL) + ((x >> 1) & 0x5555555555555555UL); x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL); x = (x & 0x0f0f0f0f0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0f0f0f0f0fUL); x = (x & 0x00ff00ff00ff00ffUL) + ((x >> 8) & 0x00ff00ff00ff00ffUL); x = (x & 0x0000ffff0000ffffUL) + ((x >> 16) & 0x0000ffff0000ffffUL); x = (x & 0x00000000ffffffffUL) + ((x >> 32) & 0x00000000ffffffffUL); return (int)x; } public static int Popcount(int x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff); return x; } public static int Ctz(long x) { if (x == 0) return -1; return Popcount((ulong)((x & -x) - 1)); } public static int SafeMod(int x, int m) { int r = x % m; return r < 0 ? r + m : r; } public static long SafeMod(long x, long m) { long r = x % m; return r < 0 ? r + m : r; } public static int Sign(long x) => x == 0 ? 0 : (x < 0 ? -1 : 1); public static int DigitSum(long n, int d = 10) { long s = 0; while (n > 0) { s += n % d; n /= d; } return (int)s; } public static long Floor(long a, long b) => a >= 0 ? a / b : (a + 1) / b - 1; public static long Ceil(long a, long b) => a > 0 ? (a - 1) / b + 1 : a / b; public static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b); public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b); public static void Swap(ref int x, ref int y) { x ^= y; y ^= x; x ^= y; } public static void Swap(ref long x, ref long y) { x ^= y; y ^= x; x ^= y; } public static void Swap(ref T x, ref T y) { T t = y; y = x; x = t; } public static T Clamp(T x, T l, T r) where T : IComparable => x.CompareTo(l) <= 0 ? l : (x.CompareTo(r) <= 0 ? x : r); public static T Clamp(ref T x, T l, T r) where T : IComparable => x = x.CompareTo(l) <= 0 ? l : (x.CompareTo(r) <= 0 ? x : r); public static void Chmin(ref T x, T y) where T : IComparable { if (x.CompareTo(y) > 0) x = y; } public static void Chmax(ref T x, T y) where T : IComparable { if (x.CompareTo(y) < 0) x = y; } public static int LowerBound(in T[] arr, Func comp, int l = -1, int r = -1) { if (arr.Length == 0) return -1; if (l == -1) l = 0; if (r == -1) r = arr.Length; while (l < r) { int x = (l + r) / 2; if (comp(arr[x]) < 0) l = x + 1; else r = x; } return l; } public static int LowerBound(in List list, Func comp, int l = -1, int r = -1) { if (list.Count == 0) return -1; if (l == -1) l = 0; if (r == -1) r = list.Count; while (l < r) { int x = (l + r) / 2; if (comp(list[x]) < 0) l = x + 1; else r = x; } return l; } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } private readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) throw new EndOfStreamException(); if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } public string Line() { var sb = new StringBuilder(); for (var b = Char(); b != 10 && !isEof; b = (char)read()) sb.Append(b); return sb.ToString(); } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public long Integer() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public ulong UInteger() { ulong ret = 0; byte b = 0; do b = read(); while (b < '0' || '9' < b); for (; true; b = read()) { if (b < '0' || '9' < b) return ret; else ret = ret * 10 + b - '0'; } } public double Double() { return double.Parse(Scan()); } } class ModFact { ModInt[] fact; ModInt[] factinv; ModInt[] inv; public ModFact(long n) { fact = new ModInt[n + 1]; factinv = new ModInt[n + 1]; inv = new ModInt[n + 1]; fact[0] = 1; for (long i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1); factinv[n] = fact[n].Inv(); for (long i = n; i > 0; i--) factinv[i - 1] = factinv[i] * i; for (long i = 1; i <= n; i++) inv[i] = fact[i - 1] * factinv[i]; } public ModInt Fact(long n) => fact[n]; public ModInt FactInv(long n) => factinv[n]; public ModInt Inv(long n) { if (n == 0) throw new DivideByZeroException(); return inv[n]; } public ModInt Binom(long n, long k) { if (n < 0) return 0; if (n == 0) return k == 0 ? 1 : 0; return 0 <= k && k <= n ? fact[n] * factinv[k] * factinv[n - k] : 0; } } struct ModInt { public static long MOD = 998244353; public long Val { get; private set; } public ModInt(long v) { Val = SafeMod(v, MOD); } public override string ToString() { return Val.ToString(); } public override bool Equals(object obj) => obj is ModInt other && this.Equals(other); public bool Equals(ModInt x) => Val == x.Val; public override int GetHashCode() => Val.GetHashCode(); public static bool operator ==(ModInt a, ModInt b) { return a.Val == b.Val; } public static bool operator !=(ModInt a, ModInt b) { return a.Val != b.Val; } public static implicit operator ModInt(long n) => new ModInt(SafeMod(n, MOD)); public static ModInt operator +(ModInt a, ModInt b) { long r = a.Val + b.Val; return new ModInt(r < MOD ? r : r - MOD); } public static ModInt operator -(ModInt a, ModInt b) { long r = a.Val - b.Val; return new ModInt(r < 0 ? r + MOD : r); } public static ModInt operator -(ModInt a) => new ModInt(a.Val == 0 ? 0 : MOD - a.Val); public static ModInt operator *(ModInt a, ModInt b) => new ModInt(a.Val * b.Val % MOD); public static ModInt operator /(ModInt a, ModInt b) => a * b.Inv(); public ModInt Pow(long n) { long t = Val, r = 1; while (n > 0) { if ((n & 1) == 1) r = r * t % MOD; t = t * t % MOD; n >>= 1; } return new ModInt(r); } public ModInt Inv() { var r = Gcd(Val, MOD); Debug.Assert(r.g == 1); return r.x; } private static (long x, long y, long g) Gcd(long a, long b) { if (b == 0) return a >= 0 ? (1, 0, a) : (-1, 0, -a); long c = a % b; if (c < 0) c += b; var r = Gcd(b, c); long x = SafeMod(r.y, b); long g = r.g; long y = (g - a * x) / b; return (x, y, g); } private static long SafeMod(long x, long m) { long r = x % m; return r < 0 ? r + m : r; } }