include <bits/stdc++.h>

cin>>n;
for(int i=1;i<=n;i++)
    cin>>a[i];
sort(a+1,a+n+1);
long long i=1;
while(i<n)
{
    if(a[i]==a[i+1])
    {
        j=i;
        while(a[j]==a[j+1]&&j<n)
            j++;
        k=lower_bound(a+j+1,a+n+1,2*a[i])-a-1;
        dem=i-1;
        if(k>j&&k<=n)
            dem=dem+k-(j+1)+1;
        h=(((j-i+1)*(j-i)/2))%m; // số lượng phần tử giống nhau
        kq=(kq+(dem*h)%m)%m;
        if(j-i+1>2)
            kq=(kq+(h*(h-1)*(h-2)/6)%m)%m;
        i=j+1;
    }
    else
        i++;
}
cout<<kq;
return 0;