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
#include <bits/stdc++.h>
using namespace std;
const int MX=5005,md=1000000007;
int n,r,i,j,a[MX],f[MX];
int main() {
  scanf("%d",&n); r=1;
  for (i=0; i<n; i++) {
    scanf("%d",&a[i]);
    r*=2; if (r>=md) r-=md;
  }
  if (--r<0) r+=md;
  sort(a,a+n);
  f[1]=1;
  for (i=0; i<n; i++) {
    for (j=5000; j>=2*a[i]; j--) {
      f[j]+=f[j-a[i]];
      if (f[j]>=md) f[j]-=md;
    }
    for (j=a[i]-1; j>0; j--) if (f[j]) {
      r-=f[j]; if (r<0) r+=md;
      f[j]*=2; if (f[j]>=md) f[j]-=md;
    }
  }
  printf("%d\n",r);
  return 0;
}