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
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int arr[5000];
long long dp[5001],pow[5001];
long long mod=1000000007,result;

int main()
{
    pow[0]=1;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        pow[i+1]=(pow[i]<<1)%mod;
    }

    sort(arr,arr+n);

    dp[0]=1;
    for(int i=0;i<n;i++){
        for(int j=5000;j>=0;j--){
            if(dp[j]==0) continue;
            if(j>=arr[i]-1)
            {
                if(j+arr[i]<=5000){
                    dp[j+arr[i]]=(dp[j+arr[i]]+dp[j]);
                    if(dp[j+arr[i]]>=mod) dp[j+arr[i]]-=mod;
                }
            }
            else
            {
                result=(result+(pow[n-i]-1)*dp[j]);
                if(result>=mod) result%=mod;
                dp[j]=0;
            }
        }
    }

    result=pow[n]-result-1;
    if(result<0) result+=mod;
    if(result<0) result+=mod;

    printf("%lld",result);

    return 0;
}