Expert.
Put your skills to the test.

Problem summary

Count nonempty subsequences having an element occurring strictly more than half their length, modulo 1000000007. Choices of positions distinguish subsequences.

Constraints

1 ≤ N ≤ 2000000; 1 ≤ P[i] ≤ N.

Worked example

Official statement example.

8
1 3 4 3 3 2 3 1

104

Solution analysis

1. A nonempty subsequence has at most one strict majority, so count independently for each party and sum. If that party occurs c times, choosing i of its positions and j other positions gives a majority exactly when j<i.
2. Instead count the excluded party positions, c−i. Then t=(c−i)+j<c. For any t, Vandermonde’s identity gives sum C(c,c−i)C(N−c,j)=C(N,t). Thus the answer for this party is the binomial prefix sum C(N,0)+...+C(N,c−1).
3. Compute modular inverses of 1..maxFrequency in linear time and generate C(N,t) from C(N,t−1)·(N−t+1)/t. Store all prefix sums once, then add prefix[c−1] for every nonzero frequency c. In the example frequencies are 4,2,1,1, contributing 93+9+1+1=104.

Why it works

For a fixed party, replacing selected party positions by its excluded positions is a bijection between majority selections and pairs of sets with total size t<c, chosen from disjoint sets of sizes c and N−c. Vandermonde counts these pairs as C(N,t). Summing t<c counts exactly all selections with that majority; uniqueness of a strict majority makes the final sum disjoint. The modular recurrence computes the binomial prefixes exactly because all denominators are smaller than the prime modulus.

Watch out. Strict majority excludes ties. Count position choices, including repeated equal values, separately. The empty subsequence is never counted.

An independently written complete program with standard headers.

// Key idea: For a fixed party, replacing selected party positions by its excluded positions is a
// bijection between majority selections and pairs of sets with total size t<c, chosen from disjoint
// sets of sizes c and N−c. Vandermonde counts these pairs as C(N,t).
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const long long mod=1000000007;
    int n;
    cin>>n;
    vector<int>frequency(n+1);
    int maximum=0;
    for(int i=0;i<n;++i){
        int party;
        cin>>party;
        maximum=max(maximum,++frequency[party]);
    }
    vector<int>inverse(maximum+1),prefix(maximum);
    inverse[1]=1;
    for(int i=2;i<=maximum;++i){
        inverse[i]=static_cast<int>(mod-(mod/i)*inverse[mod%i]%mod);
    }
    long long choose=1;
    prefix[0]=1;
    for(int t=1;t<maximum;++t){
        choose=choose*(n-t+1)%mod*inverse[t]%mod;
        prefix[t]=static_cast<int>((prefix[t-1]+choose)%mod);
    }
    long long answer=0;
    for(int c:frequency){
        if(c>0){
            answer+=prefix[c-1];
        }
    }
    cout<<answer%mod<<'\n';
}