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


using namespace std;

#ifdef USE_CERR_LOG
#define LOG if (true) cerr
const bool LogEnabled = true;
#else
#define LOG if (false) cerr
const bool LogEnabled = false;
#endif

bool LogBigEnabled = true;

#ifdef USE_FILE_CIN
ifstream fin("cuk.in");
#define cin fin
#endif

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 1'000'000'007;
vector<int> bags;
vector<int> counts;
int bagCount, infTotal;


void readData() {
    ios_base::sync_with_stdio(false);
    
    cin >> bagCount;
    bags.resize(bagCount);
    
    for (int& bag : bags) {
        cin >> bag;
    }
    
    sort(bags.begin(), bags.end());
    infTotal = bags.back() + 2;
    counts.resize(infTotal + 1, 0);
    LOG << "Inf=" << infTotal << endl;
}


void printCounts() {
    #ifdef USE_CERR_LOG
        for (uint i = 0; i < counts.size(); i++) LOG << "(" << i << "," << counts[i] << ") ";
        LOG << endl;
    #endif
}


void solve() {
    for (int bag : bags) {
        vector<pair<int, int>> diffs;
        diffs.reserve(bags.size());
        
        if (bag == 1) {
            diffs.push_back({1, 1});
        }
        
        for (int i = bag-1; i < infTotal; i++) {
            if (counts[i] == 0) continue;
            
            int newVal = min(i + bag, infTotal);
            int delta = counts[i];
            diffs.push_back({newVal, delta});
        }
        
        diffs.push_back({infTotal, counts[infTotal]});
        
        for (auto& diff : diffs) {
            LOG << "[" << diff.first << "," << diff.second << "] ";
            counts[diff.first] = (counts[diff.first] + diff.second) % mod;
        }
        
        printCounts();
    }
    
    int total = 0;
    for (int count : counts) {
        total = (total + count) % mod;
    }
    
    cout << total;
}


int main() {
    readData();
    
    if (bags.front() > 1) {
        cout << 0;
    } else {
        solve();
    }
    
    return 0;
}