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
#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int A[5000];
unsigned T[5000 * 5000 + 1];

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d", &A[i]);

  sort(A, A + N);

  T[0] = 1;
  int nzix = 0;
  for (int i = 0; i < N; i++) {
    int x = A[i];
    //for (int y = 5000 * 5000 - x; y >= x-1; y--) {
    if (nzix >= x-1) {
      for (int y = nzix; y >= x-1; y--) {
        T[x + y] += T[y];
        //T[x + y] %= 1'000'000'007U;
        if (T[x + y] > 1'000'000'007U) T[x+y] -= 1'000'000'007U;
      }
      nzix += x;
    }
  }

  unsigned result = 0;
  for (int i = 1; i <= 5000 * 5000; i++) {
    result += T[i];
    //T[i] %= 1'000'000'007U;
    if (result >= 1'000'000'007U) result -= 1'000'000'007U;
  }

  printf("%u\n", result);
  return 0;
}