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
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <unordered_map>
#include <vector>

using i32 = int32_t;
using i64 = int64_t;
constexpr i32 mod = 1000000000 + 7;

constexpr i64 key(i32 a, i32 b)
{
  return ((i64)a << 32) | b;
}

i32 solve(std::vector<i32> const &V)
{
  std::vector<i32> M(V.size());
  M[0] = V[0];
  for (i32 i = 1; i < V.size(); ++i) {
    M[i] = M[i - 1] + V[i];
  }
  i32 limit = std::min(10000, M.back());
  std::vector<i32> P(limit + 1, 0);
  P[0] = 1;

  for (i32 v = 0; v < V.size(); ++v) {
    i32 lim = std::min(limit, M[v]);
    i32 sum = 0;
    for (i32 i = lim - V[v] + 1; i <= lim; ++i) {
      sum = (sum + P[i]) % mod;
    }
    for (i32 i = lim; i >= 2 * V[v] - 1; --i) {
      P[i] = (P[i] + P[i - V[v]]) % mod;
    }
    P[lim] = (P[lim] + sum) % mod;
  }

  i32 ans = 0;
  for (i32 i = 1; i <= limit; ++i) {
    ans = (ans + P[i]) % mod;
  }
  return ans;
}

int main()
{
  std::ios::sync_with_stdio(false);

  i32 n;
  std::cin >> n;

  std::vector<i32> ai(n);
  for (i32 i = 0; i < ai.size(); ++i) {
    std::cin >> ai[i];
  }

  std::sort(ai.begin(), ai.end());
  std::cout << solve(ai) << std::endl;

  return 0;
}