class Solution {
private:
    int m_cnt = 0;
public:
    
    vector<int> div(vector<int> &data, int start, int end){
        vector<int> temp;
        //temp.reserve(end-start);
        if(start==end) {temp.push_back(data[start]);return temp;}
        temp.reserve(end-start);
        int mid = (end+start)/2;
        vector<int> left = div(data, start, mid);
        vector<int> right = div(data, mid+1, end);

        int size1 = left.size();
        int size2 = right.size();

        for(int ii=0; ii<size1;ii++){
            for(int jj=0; jj<size2; jj++){
                if(left[ii]>right[jj]){
                    int cnt = size2-jj;
                    m_cnt = (m_cnt+cnt)%1000000007;
                    break;
                }
            }
        }

        int i=0, j=0;
        while(i<size1&&j<size2){
            if(left[i]>right[j]){
                temp.push_back(left[i]);
                i++;
            }else{
                temp.push_back(right[j]);
                j++;
            }
        }

        if(i>=size1){
            while(j<size2) {
                temp.push_back(right[j]);
                j++;
            }
        }

        if(j>=size2){
            while(i<size1) {
                temp.push_back(left[i]);
                i++;
            }
        }

        return temp;

    }

    int InversePairs(vector<int> data) {
        int size = data.size();
        if(size==0) return 0;
        vector<int> ans;
        ans.reserve(size);
        div(data,0,size-1);
        return m_cnt;
    }
};