1712

class Solution {
public:
    int count_bet(vector<int> &a, int ind, int low, int high) {
        if(low > high) return 0;

        auto l_itr = lower_bound(a.begin(), a.begin() + ind, low);
        auto r_itr = upper_bound(a.begin(), a.begin() + ind, high);
        return (r_itr - l_itr);
    }

    int waysToSplit(vector<int>& a) {
        int n = a.size(), mod = int(1e9)+7;
        for(int i = 1; i < n; i++)
            a[i] += a[i - 1];

        int sum = a[n-1];
        long long cnt = 0;
        int suf = 0;

        for(int i = n - 1; i >= 2; i--){
            suf = a[n-1]-a[i-1];
            auto in_bet = count_bet(a, i - 1, sum - 2*suf, (sum - suf)/2);
            cnt = (cnt + in_bet) % mod;
        }
        return cnt;
    }
};