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

using namespace std;

const int M = 5005;
const int64_t P = 1e9+7;
int64_t dp[M];
int a[M];

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

  int n;
  cin >> n;

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

  sort(a, a+n);

  dp[0] = 1;

  for(int i = 0; i < n; ++i) {
    for(int j = 5000; j >= a[i]-1; --j) {
      dp[min(5000, j+a[i])] = (dp[min(5000, j+a[i])] + dp[j])%P;
    }
  }
  int64_t sum = 0;
  for(int i = 1; i <= 5000; ++i)
    sum = (sum+dp[i])%P;
  
  cout << sum << '\n';
}