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
#include <stdio.h>
#include <stdlib.h>
#include <climits>
#include <map>

#define P (1000LL*1000LL*1000LL+7LL)

long long int ok(long long int r) {
  return r % P;
}

using namespace std;
/*struct BOX {
  long long int bon;
  long long int com;
};*/

//BOX boxes_stash[5010*5010];
long long int pascal[5020][5020];

map<long long int, long long int> boxes;
map<long long int, long long int> bon;
map<long long int, long long int> mods;
map<long long int, long long int> bon_add;
map<long long int, long long int>::iterator it, it2, it3;

/*int compare_asc(const void *arg1, const void *arg2) {
  return *(int*)arg1 - *(int*)arg2;
}*/

int main() {
  long long int n, a;
//  int a[5001];

  for(int i = 0; i <= 5010; i++) {
    for(int j = 0; j <= 5010; j++) {
      pascal[i][j] = 0LL;
    }
  }
  pascal[0][0] = 1LL;
  for(int i = 1; i <= 5000; i++) {
    pascal[i][0] = 1LL;
    for(int j = 1; j <= i; j++) {
      pascal[i][j] = ok(pascal[i-1][j] + pascal[i-1][j-1]);
    }
  }
//  printf("%lld    \n", pascal[4][0]);
//  printf("%lld    \n", pascal[4][1]);
//  printf("%lld    \n", pascal[4][2]);
//  printf("%lld    \n", pascal[4][3]);
//  printf("%lld    \n", pascal[4][4]);
// // printf("%lld    \n", pascal[3][1]);

  scanf("%lld", &n);
  for(int i = 0; i <  n; i++) {
    scanf("%lld", &a);//&(a[i]));
    int b = 0LL;
    it = boxes.find(a);
    if(it != boxes.end()) {
      b = it->second;
      boxes.erase(it);
    }
    boxes.insert({a, b + 1LL});
  }

  bon.insert({0LL, 1LL});

//  for(it = boxes.begin(); it != boxes.end(); ++it) {
//  }

  for(it = boxes.begin(); it != boxes.end(); ++it) {
    long long int bf = it->first;
    long long int bs = it->second;
    for(long long int i = 1LL; i <= bs; i++) {
      long long int plus = ok(i * bf);
//      printf("PLUS=%lld\n", plus);
      long long int times = pascal[bs][i];
      for(it2 = bon.begin(); it2 != bon.end(); ++it2) {
        long long int f = it2->first;
        long long int s = it2->second;
        if(f < bf-1) {
          continue;
        }
        bon_add.insert({f+plus, ok(times * s)});
      }
    }

    for(it2 = bon_add.begin(); it2 != bon_add.end(); ++it2) {
      it3 = bon.find(it2->first);
      long long int total = it2->second;
      if(it3 != bon.end()) {
        total = ok(total + it3->second);
        bon.erase(it3);
      }
      bon.insert({it2->first, total});
    }
    bon_add.clear();
  }

//  a[n] = INT_MAX;

//   qsort(a, n, sizeof(*a), compare_asc);
  long long int ret = -1LL;
  for(it = bon.begin(); it != bon.end(); ++it) {
    ret = ok(ret + it->second);
  }

/*  for(it = boxes.begin(); it != boxes.end(); ++it) {
    printf("%lld#%lld, ", it->first, it->second);
  }
  printf("\n\n\n");
  for(it = bon.begin(); it != bon.end(); ++it) {
    printf("%lld#%lld, ", it->first, it->second);
  }
  printf("\n\n\n");*/
  printf("%lld", ret);
  return 0;
}