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
//runda 5C
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

#define sumuj(a, b) ((long long)a + b) % 1000000007LL

struct Suma {
  long long suma;
  mutable int ilosc;
  Suma(int s, long long i):suma(s), ilosc(i) {}
  bool operator<(const Suma& rhs) const {
    return suma > rhs.suma;
  }
};

long long kolejka0[13000000];
int kolejka1[13000000];
int kolWsk;

int main() {
  ios_base::sync_with_stdio(0);
  int n, a;
  vector<int> we;
  set<Suma> sumy;
  int aktSuma;
  long long wynik;
  pair<set<Suma>::iterator, bool> ret;

  cin >> n;
  we.reserve(n);
  for(int iN = 0; iN < n; ++iN) {
    cin >> a;
    we.push_back(a);
  }
  sort(we.begin(), we.end());

  if(we[0] != 1) {
    cout << 0;
    return 0;
  }

  sumy.insert(Suma(0, 1));
  sumy.insert(Suma(1, 1));
  aktSuma = 1;
  wynik = 1;

  for(int iN = 1; iN < n; ++iN) {
    if(we[iN] > (aktSuma + 1))
      break;
    aktSuma += we[iN];
    kolWsk = -1;
    for(auto i = sumy.begin(); i != sumy.end(); ++i)
      if((i->suma + 1) >= we[iN]) {
        kolejka0[++kolWsk] = i->suma + we[iN];
        kolejka1[kolWsk] = i->ilosc;
        wynik = sumuj(wynik, i->ilosc);
      } else
        break;
    for(int i = 0; i <= kolWsk; ++i) {
      ret = sumy.insert(Suma(kolejka0[i], kolejka1[i]));
      if(!ret.second)
        ret.first->ilosc = sumuj(ret.first->ilosc, kolejka1[i]);
    }
  }
  cout << wynik;
  return 0;
}