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
#include <cstdio>
#include <set>
#include <map>

#define M 1000000007

int main ()
{
  std::multiset <int> m;
  int n;
  scanf ("%i", &n);
  while (n--)
  {
    int a;
    scanf ("%i", &a);
    m.emplace (a);
  }
  std::map <int, int> t;
  for (auto i=m.begin(); i!=m.end(); ++i)
  {
    for (auto j=t.end(); j!=t.begin();)
    {
      --j;
      if (j->first < *i-1) break;
      (t[j->first + *i] += j->second) %= M;
    }
    if (*i == 1) t[1]++;
  }
  int c = 0;
  for (auto j=t.begin(); j!=t.end(); ++j) (c += j->second) %= M;
  printf ("%i\n", c);
  return 0;
}