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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 1'000'000'007;
const int MAX = 5001;

int dp[2][MAX + 1];

#ifdef LOCAL
#define debug(cur, Z) { for (int z = 0; z <= Z; z++) { cout << dp[cur][z] << " "; } cout << endl; }
#else
#define debug(...) {}
#endif

void solve(int n, vector<int> a) {
  sort(a.begin(), a.end());
  
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    int cur = (i % 2 == 0);
    int old = 1 - cur;

    for (int j = 0; j < MAX; j++) {
      dp[cur][j] = dp[old][j];
      if (2 * a[i] - 1 <= j) {
        dp[cur][j] = (dp[cur][j] + dp[old][j - a[i]]) % MOD;
      }
    }
    
    dp[cur][MAX] = dp[old][MAX];
    for (int j = max(a[i] - 1, MAX - a[i]); j <= MAX; j++) {
      dp[cur][MAX] = (dp[cur][MAX] + dp[old][j]) % MOD;
    }

  }

  int res = 0;
  int cur = ((n - 1) % 2 == 0);
  for (int j = 1; j <= MAX; j++) {
    res = (res + dp[cur][j]) % MOD;
  }

  cout << res << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  solve(n, a);
}