1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5000, MOD = 1e9+7;
int n, a[N], dp[N+1];
void add(int &x, int y) { x = (x + y) % MOD; }
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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 s=N; s>=a[i]-1; s--)
            add(dp[min(s+a[i], N)], dp[s]);
    int res = 0;
    for (int i=0; i<=N; i++) add(res, dp[i]);
    cout << (res+MOD-1) % MOD << "\n";
    return 0;
}