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 <bits/stdc++.h>
using namespace std;

vector<long long> pd(25000001);
set<int,greater<int> > S;
set<int,greater<int> >::iterator sit;

int main() {
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i=0;i<n;i++)
		cin >> v[i];
	sort(v.begin(),v.end());
	int s=0;
	pd[0]=1;
	S.insert(0);
	vector<int> add;
	for (int i=0;i<n;i++) {
		//cout << v[i] << endl;
		add.clear();
		for (sit=S.begin();sit!=S.end() && v[i]<= *sit+1;sit++) {
			//cout << "*s=" << *sit << endl;
			if (pd[*sit]) {
				add.push_back(*sit+v[i]);
				pd[*sit+v[i]]=(pd[*sit+v[i]]+pd[*sit])%1000000007;
			}
		}
		for (int i=0;i<add.size();i++)
			S.insert(add[i]);
		//for (sit=S.begin();sit!=S.end();sit++) cout << *sit; cout << endl;
	}
	long long answer = 0;
	for (sit=S.begin();sit!=S.end() && *sit>0;sit++) 
		answer = (answer+pd[*sit])%1000000007;
	cout << answer;
	return 0;
}