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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
const int N = 5e3+2;
int n, a[N];
ll dp[N];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.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 j=N-1; j>=a[i]-1; --j) {
			dp[min(N-1, j+a[i])] = (dp[min(N-1, j+a[i])] + dp[j])%mod;
		}
	}
	ll ans = 0;
	for(int i=1; i<N; ++i) {
		ans = (ans + dp[i])%mod;
	}
	cout<<ans;
}