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

using namespace std;

const int inf = 1e9 + 7;

int n, M;
vector<int> v, odp;
int dp[5005][5005];
int pref[5005][5005];

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n;
  v.resize(n);
  for (int& i : v)
  {
    cin >> i;
    M = M < i ? i : M;
  }
  sort(v.begin(), v.end());

  if (v[0] != 1)
  {
    cout << "0\n";
    return 0;
  }

  // dp[i][j] = ilosc dobrych podzbiorow [0, i] o sumie dokladnie j
  dp[0][1] = 1;
  for (int i = 1; i < n; i++)
    for (int j = 1; j <= M; j++)
    {
      int tmp = dp[i - 1][j - v[i]] * (j >= 2 * v[i] - 1) + dp[i - 1][j] + (v[i] == (j == 1));
      dp[i][j] = tmp >= inf ? tmp - inf : tmp;
    }

  // pref[i][j] = ilosc dobrych podzbiorow [0, i] o sumie <= j
  for (int i = 0; i < n; i++)
    for (int j = 1; j <= M; j++)
    {
      int tmp = pref[i][j - 1] + dp[i][j];
      pref[i][j] = tmp >= inf ? tmp - inf : tmp;
    }

  // odp[i] = ilosc dobrych podzbiorow [0, i]
  int odp = 1;
  /*for (; i < n && v[i] == 1; i++)
  {
    odp = 2 * odp + 1;
    odp = odp > inf ? odp - inf : odp;
  } */
  for (int i = 1; i < n; i++)
  {
    odp = 2 * odp - pref[i - 1][v[i] - 2] + (v[i] == 1);
    if (odp < 0)
      odp += inf;
    else if (odp >= inf)
      odp -= inf;
  }
  cout << odp << '\n';
}