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

using namespace std;

unsigned short int n;
unsigned long long int possibleCombinations = 0;

void check(unsigned short int packages[], unsigned short int index, unsigned long long int sum) {
    while (true) {
        if (index < n && packages[index] <= sum + 1) {

            if (index + 1 < n && packages[index + 1] <= sum + 1) {
                //cout << "rekurencja!" << endl << endl;
                check(packages, index + 1, sum);
            }

            sum += packages[index];
            possibleCombinations = (possibleCombinations + 1) % 1000000007;
            index++;

            //cout << "Suma po: " << sum << endl;
            //cout << "Kombinacje po: " << possibleCombinations << endl;
            //cout << "Index po: " << index << endl << endl;
        }
        else {
            //cout << "koniec tego!" << index << endl << endl;
            break;
        }
    }
}


int main()
{
    cin >> n;
    unsigned short int* packages = new unsigned short int[n];

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

    sort(packages, packages + n);

    if (packages[0] == 1) {
        check(packages, 0, 0);

        cout << possibleCombinations;
    }
    else {
        cout << 0;
    }
}