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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cassert>
#include <cstdint>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <vector>

#if !TS_DEBUG
#define NDEBUG
#endif

typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

typedef uint8_t u8;


class Tab {
    i32 _rows;
    i32 _columns;
    std::unique_ptr<i32[]> _data;

    public:
    Tab(i32 rows, i32 columns)
        : _rows(rows), _columns(columns), _data(new i32[rows * columns])
    {}

    i32 * operator[](i32 row) { return row * _columns + _data.get(); }

    i32 & operator()(i32 row, i32 column) {
        return _data[row * _columns + column];
    }
};

class Num {
public:
    static const i32 M = 1000000007;

    Num() : _x(0) {}

    static Num of(i32 a) {
        assert(0 <= a);
        return Num(a % M);
    }

    void operator+=(Num a) {
        assert(0 <= _x);
        assert(_x < M);
        assert(0 <= a._x);
        assert(a._x < M);
        auto x = _x + a._x;
        _x = (M <= x) ? x - M : x;
        assert(0 <= _x);
        assert(_x < M);
    }

    void operator-=(Num a) {
        assert(0 <= _x);
        assert(_x < M);
        assert(0 <= a._x);
        assert(a._x < M);
        auto x = _x - a._x;
        _x = (x < 0) ? x + M : x;
        assert(0 <= _x);
        assert(_x < M);
    }

    void operator++() {
        assert(0 <= _x);
        assert(_x < M);
        _x++;
        if (M <= _x)
            _x -= M;
        assert(0 <= _x);
        assert(_x < M);
    }

    bool IsZero() { return _x == 0;}

    friend std::ostream & operator<<(std::ostream & s, Num num);

private:
    i32 _x;
    Num(i32 x) : _x(x) {
        assert(0 <= x);
        assert(x < M);
    }
};

std::ostream & operator<<(std::ostream & s, Num num) {
    return s << num._x;
}

const i32 MAX_N = 5000;
const i32 MAX_A = 5000;

i32 C[MAX_N + 1];
Num R[MAX_N * MAX_A + 1];


int main()
{
    i32 n;
    std::cin >> n;

    i32 amax = 0;
    for (i32 i = 0; i < n; i++) {
        i32 a;
        std::cin >> a;
        amax = std::max(a, amax);
        C[a]++;
    }

    i32 s = 0;
    R[0] = Num::of(1);
    Num r;

    for (i32 a = 1; a <= amax; a++) {
        i32 c = C[a];
        if (c == 0) continue;        
        if (s < a - 1) break;
        for (i32 i = 0; i < c; i++) {
            for (i32 j = s; j >= a - 1; j--) {
                auto rj = R[j];
                if (rj.IsZero()) continue;
                R[j + a] += rj;
                r += rj;
            }
            s += a;
        }
    }

    std::cout << r << '\n';

    return 0;
}