#include #include #include #include #include #include #include #include #include #include using namespace std; #define MOD 1000000007 //n! mod p table long long fact[400000+1]; void make_fact(long long p){ fact[0] = 1; for(int i=1; i<=400000; i++){ fact[i] = ((long long)fact[i-1]*i%p)%p; } } long long extgcd(long long a, long long b, long long &x, long long &y){ long long d=a; if(b!=0){ d = extgcd(b, a%b, y, x); y -= (a/b) * x; }else{ x = 1; y = 0; } return d; } long long mod_inverse(long long a, long long m){ long long x,y; extgcd(a,m,x,y); return (m+x%m)%m; } long long mod_fact(long long n, long long p, long long &e){ e = 0; if(n==0) return 1; long long res = mod_fact(n/p, p, e); e += n/p; if(n/p %2 != 0) return res * (p-fact[n%p]) %p; return res * fact[n%p]%p; } //nCk mod p long long mod_comb(long long n, long long k, long long p){ if(n<0 || k<0 || n e2+e3) return 0; return a1 * mod_inverse(a2*a3 %p, p) %p; } int main(){ make_fact(MOD); int N; cin >> N; vector cnt(5000, 0); vector A(N); for(int i=0; i> A[i]; cnt[A[i]]++; } long long ans = 0; vector dp(N+1, 0); dp[0] = 0; for(int i=0; i