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
#include <iostream>

using namespace std;

const unsigned long long int N=6015, M=1000000007;
int tab[N];

int main()
{
    unsigned long long int n,a,wyn=0,il=1,sum=0,dod,pom;
    int ostatni=0,p2;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        tab[a]++;
    }
    for(int i=1;i<N;i++)
    {
        if(tab[i]==0)
            continue;
        if(i>sum+1)
            {cout<<wyn<<"\n"; return 0;}
        p2=0;
        while(sum-tab[ostatni]*ostatni + ostatni*(p2+1) < i && p2<tab[ostatni])
            p2++;
        if(ostatni!=0)
            il=tab[ostatni]-p2+1;
        sum=min(sum+i*tab[i],M);
        if(tab[i]==1)
            wyn=(il+wyn)%M;
        else if(tab[i]>1)
        {

            pom=tab[i]; dod=pom;
            for(int j=1;j<tab[i];j++)
            {
                pom=(pom*(tab[i]-j)/(j+1));
                dod=(pom+dod)%M;
            }
            il=(dod*il)%M;
            wyn=(il+wyn)%M;
        }
        ostatni=i;
    }
    cout<<wyn<<"\n";
    return 0;
}