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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <set>
#include <map>
#include <utility>
#include <deque>
#include <vector>
#include <algorithm>
#include <stdexcept>

constexpr int MAX = 5001;
constexpr long MOD = 1000000007;
int n;
int inputs[MAX];
int jump_down[MAX * MAX];
int jump_up[MAX * MAX];
long counts[MAX * MAX];
long max_count = 0;
long result = 0;
int ones = 0;
int non_ones = 0;

// 1
// 2 1
// 3 3 1
// 6 6 4 1

int main() {
  scanf("%d\n", &n);
  for (int i=0; i<n; i++) {
    int input;
    scanf("%d", &input);
    if (input == 1) {
      ones ++;
    } else {
      inputs[non_ones++] = input;
    }
  }
  for (int i=0; i<ones; i++) {
    for (int j = i + 1; j >= 2; j--) {
      counts[j] = (counts[j] + counts[j-1]) % MOD;
    }
    counts[1]++;
  }
  max_count = ones;
  for (int i=1; i<=max_count; i++) {
    result = (result + counts[i]) % MOD;
    jump_down[i] = i-1;
    jump_up[i-1] = i;
  }
  std::sort(inputs, inputs + non_ones);
  for (int i =0 ; i< non_ones; i++) {//
    int input = inputs[i];
    // printf("input = %d\n", input);
    // fflush(stdout);
    
    int c = max_count;
    while(c >= input - 1) {
      //  printf("c = %d\n", c);
      //  fflush(stdout);
      int ci = c + input;
      //  printf("ci = %d\n", ci);
      //  fflush(stdout);
      result = (result + counts[c]) % MOD;
      int counts_ci_prev = counts[ci];
      counts[ci] = (counts[ci] + counts[c]) % MOD;
      if (counts_ci_prev == 0 && counts[ci] > 0) {
        if (c == max_count) {
          max_count = ci;
        }
        if (jump_down[ci] == 0) {
          int d = ci - 1;
          while (d > 0 && counts[d] == 0) {
            d --;
          }
          if (counts[d] > 0) {
            jump_down[ci] = d;
            jump_up[ci] = jump_up[d];
            if (jump_up[d] > 0) {
              jump_down[jump_up[d]] = ci;
            }
            jump_up[d] = ci;
          }
        }
      }
      c = jump_down[c];
    }
    
    //
    // for (int j =0 ;j<=max_count; j++) {
    //   printf("counts[%d]=%ld\n", j, counts[j]);
    // }//////
  }
  // for (int i=0; i<=max_count; i++) {
  //   printf("%d: %d %d\n", i, counts[i], jump_to[i]);
  // }
  printf("%ld\n", result);
  return 0;
}