#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

#define MAXSIZE 1000


int *seq;

int cmp1(const void *a, const void *b) {
    return seq[*(int*)a] - seq[*(int*)b];

}

int *facts;

int fact(int num) {
    int ix = num;
    int result = 1;
    while(facts[ix] == 0) {
        --ix;
    }
    result *= facts[ix];
    while(ix < num) {
        ++ix;
        result *= ix;
        facts[ix] = result;
    }
    return result;
}


int main(void) {
    facts = new int[1000+1];
    for(int ii =1; ii < 1001; ++ii)
        facts[ii] = 0;
    facts[0]=1;
    int n;
    FILE *in = fopen("median.in", "rt");
    
    fscanf(in, "%d", &n);
    seq = new int[n];
    int *ord1 = new int[n];
    int *result = new int[n];
    
    for(int ii = 0; ii < n; ++ii) {
        fscanf(in, "%d", &(seq[ii]));
        ord1[ii] = ii;
    }
    
    fclose(in);
    
    qsort(ord1, n, sizeof(int), cmp1);
    
    for(int ii = 0; ii < n; ++ii) {
        // ii is the sorted index
        // ix is the original index
        int ix = ord1[ii];
        int elem = seq[ix];
        result[ix] = 1;
        for(int jj = 2; ; ++jj) {
            int k = jj/2;
            int chl, chr, ofl, ofr;
            if(jj % 2 == 1) {
                chl = k;
                chr = k;
                ofl = ii;
                ofr = n - ii - 1;
            }
            else {
                chl = k;
                chr = k-1;
                ofl = ii;
                ofr = n - ii - 1;
            }
            // cout<<elem<<" "<<ofl<<" "<<chl<<" "<<ofr<<" "<<chr<<" "<<left<<" "<<right<<"\n";
            if(ofl < chl || ofr < chr)
                break;
            int left = fact(ofl)/(fact(chl)*fact(ofl-chl));
            int right = fact(ofr)/(fact(chr)*fact(ofr-chr));
            
            result[ix] += (left % 1000007) * (right % 1000007);
            result[ix] %= 1000007;
        }
    }
    
    
    FILE* out = fopen("median.out", "wt");
    fprintf(out, "%d", result[0]);
    for(int ii = 1; ii < n; ++ii) {
        fprintf(out, " %d", result[ii]);
    }
    fclose(out);
    
	return 0;
}



















<!-- 0.0402s -->