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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <map>
#include <tuple>
#include <algorithm>
#include <vector>

using namespace std;

int mod(int i) {
	return i % 1000000007;
}

int main()
{
	int n;
	cin >> n;
	vector<int> data(n);
	for (int x = 0;x < n;x++) {
		int t;
		cin >> t;
		data[x] = t;
	}
	sort(data.begin(), data.end());
	map<int, int> roz;
	if (data.front() != 1) {
		cout << "0";
		return 0;
	}
	roz.insert({ 0,1 });
	vector<int>::iterator it = data.begin();
	vector<tuple<int, int> > tmp;
	//it++;

	while (it != data.end()) {
		map<int, int>::iterator setit = roz.end();
		setit--;
		if (setit->first < *it - 1) break;
		while (setit->first >= *it - 1)
		{
			tmp.push_back({ setit->first + *it, setit->second});

			if (setit == roz.begin()) break;
			setit--;
		}

		for (vector<tuple<int, int> >::iterator tmpit = tmp.begin(); tmpit != tmp.end(); tmpit++) {
			map<int, int>::iterator f = roz.find(get<0>(*tmpit));
			if (f == roz.end()) {
				roz[get<0>(*tmpit)] = get<1>(*tmpit);
			}
			else {
				f->second += get<1>(*tmpit);
				f->second = mod(f->second);
			}
		}

		tmp.clear();
		it++;
	}

	int odp = 0;

	map<int, int>::iterator sit = roz.begin();
	sit++;

	for (;sit != roz.end(); sit++) {
		odp += sit->second;
		odp = mod(odp);
	}

	cout << odp;
	return 0;
}