1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;

const LL M = 1000000007;
const LL MAX = 5005;//5005*5005;//5005;
LL n;
LL a[5005];
LL dp[2][MAX];
LL res;


LL power(LL x, int y, int p){
    LL res = 1;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Returns n^(-1) mod p
LL modInverse(LL n, int p){
    return power(n, p - 2, p);
}
 
// Returns nCr % p using Fermat's little
// theorem.
LL nCrModPFermat(LL n, int r, int p){
    if (n < r)
        return 0;
    if (r == 0)
        return 1;
    LL fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;
 
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}



int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(LL i=1; i<=n; i++){
		LL tmp;
		cin>>tmp;
		a[tmp]++;
	}
	dp[0][1]=1;
	LL last = 1;
	LL next_last = 1;
	for(LL i=1; i<MAX; i++){
		LL tmp = a[i];
		if(last < i)
			break;
		LL sum = 0;
		if(tmp==0)
			continue;
		while(tmp){
			sum = nCrModPFermat(a[i], tmp, M);
			next_last = max(next_last, last+i*tmp);
			LL end=MAX;
			LL to_add = 0;
			for(LL j=min(last+i*tmp , MAX-1); j>=i*tmp+i; j--){
				dp[1][j] = (dp[1][j] + (dp[0][j - i*tmp] * sum)) % M + M;
				end=j;
			}
			to_add = (dp[0][i] * sum) % M + M;
			for(LL j=end-1; j>i; j--){
				dp[1][j] = (dp[1][j] + to_add) % M + M;
			}
			tmp--;
		}
		for(LL j=min(next_last, MAX-1 ); j>i; j--){
			if(dp[1][j] == 0)
				dp[1][j]=dp[1][j+1];
		}
		last=next_last;
		for(LL j=0; j<=min(last, MAX-1); j++){
			dp[0][j] = (dp[0][j] + dp[1][j]) % M + M;
			dp[1][j] = 0;
		}
	}
	for(LL i=1; i<5005; i++){
		res = (res + dp[0][i] * (power(2, a[i], M) - 1) ) % M + M;
	}
	cout<<res%M<<"\n";
	
	return 0;
}