[C++] || Prefix-Sum and Binary Search With Explanation
IDEA\n Iterate at every index i in nums array and keep the left porition upto ith index(i included).\n Now we want to find the middle portion and right portion 
* **IDEA**\n* Iterate at every index `i` in nums array and keep the left porition upto ith index(`i` included).\n* Now we want to find the middle portion and right portion such that `left <= middle` and `middle  <= right`.\n* Find the ending index of middle array- `middleStart` (in prefix sum array ), which would be at least `2*prefixSum[i]`.(Because when we find the actual sum of middle array we would be subtracting the left sum part which is not a part of middle array. Therefore, the middleSum Should be atleast twice the left sum).Middle array cannot end before this index because then left would be smaller than middle sum. Therefore , middle sum has to include the middleStart position atleast.   \n* Now the index which has to be included in middle array to satisfy `leftSum <= middleSum` has been determined.\n* Now assume you are given an array and you have to find the number of positions such that sum of left part <= sum of right part. This can be easily determined by binary Search. These Positions will be the possible ending positions of middle array. Keep Adding these positions to ways .   \n\n```\nclass Solution {\npublic:\n    int MOD = 1e9 + 7 ;\n    int ways = 0 ;\n    vector<int>pref,suff ;\n    \n    void Build_Prefix(vector<int>&nums){\n        for(int i = 0 ; i < nums.size() ; ++i ){\n            if(!i) pref.push_back(nums[i]) ;\n            else pref.push_back(pref.back() + nums[i]) ;\n        }\n    }\n    \n    void Build_Suffix(vector<int>&nums){\n        for(int i = nums.size() - 1 ; i >= 0 ; --i ){\n            if(i == nums.size() - 1) suff.push_back(nums[i]) ;\n            else suff.push_back(suff.back() + nums[i]) ;\n        }\n        reverse(begin(suff),end(suff)) ;\n    }\n    \n    int countWays(vector<int>&pref , vector<int>&suff , int middleStart , int left ){\n        int idx = -1 ;\n        int lo = middleStart , hi = pref.size() - 2 ;\n        while(lo <= hi){\n            int mid = lo + (hi-lo) / 2 ;\n            //if left sum at mid position is less than equal to right sum then move forward\n            //because we want to find max position upto which condition is satisfied\n            if(pref[mid] - left <= suff[mid + 1]){\n                idx = mid ; \n                lo = mid + 1 ;\n            } else hi = mid - 1 ;\n        }\n        \n        if(idx == -1) return 0 ;\n        //Number of positions where middle array can end and condition will still be satisfied \n        return idx - middleStart + 1 ;\n        \n    }\n    int waysToSplit(vector<int>& nums) {\n        Build_Prefix(nums) ; Build_Suffix(nums) ;\n        \n        for(int i = 0 ; i < pref.size() ; ++i ){\n            int left = pref[i] , least = 2*left ;\n            int middleStart = lower_bound(begin(pref) + i + 1,end(pref),least) - begin(pref) ;\n            ways =  (ways % MOD + countWays(pref,suff,middleStart,left) % MOD) % MOD ;\n        }\n        \n        return ways ;\n        \n    }\n};\n```
['C']