Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"


Example 2:

Input: s = "1001"
Output: 0


Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 105
	s[i] is either '0' or '1'.


class Solution:
    def numWays(self, s: str) -> int:
        ones = 0

        # Count number of Ones
        for char in s:
            if char == "1":
                ones += 1

        # Can't be grouped equally if the ones are not divisible by 3
        if ones > 0 and ones % 3 != 0:
            return 0

        # Ways of selecting two dividers from n - 1 dividers 
        if ones == 0:
            n = len(s)
			# n = {3: 1, 4: 3, 5: 6, 6: 10, 7: 15 ... }
            return (((n - 1) * (n - 2)) // 2) % ((10 ** 9) + 7)

        # Number of ones in each group
        ones_interval = ones // 3

        # Number of zeroes which lie on the borders
        left, right = 0, 0

        # Iterator
        i = 0
        temp = 0

        # Finding the zeroes on the left and right border
        while i < len(s):
            temp += int(s[i]) & 1
            if temp == ones_interval:
                if s[i] == '0':
                    left += 1
            if temp == 2 * ones_interval:
                if s[i] == '0':
                    right += 1
            i += 1
        
        # The result is the product of number of (left + 1) and (right + 1)
        # Because let's assume it as we only want to fill up the middle group
        # The solution would be if we have zero then there might be a zero in the middle
        # Or there might not be the zero, so this might case is added and then
		# the events are independent so product of both the events
        return ((left + 1) * (right + 1)) % ((10 ** 9) + 7)
class Solution {
    public int numWays(String s) {
        long n=s.length();
        long one=0;//to count number of ones
        long mod=1_000_000_007;
        char[] c=s.toCharArray();
        for(int i=0;i<c.length;i++)
        {
            if(c[i]=='1')
                one++;
        }
        
             //there will be 3 cases
            // 1.no ones present in the string
            // 2.number of ones present in the string isnt divisible by 3(since we need to cut 3 parts)
            // 3.number of ones divisible by 3
        
        if(one==0)//case 1
        {
            return (int)((((n-1)*(n-2))/2)%mod);
        }
        if(one%3!=0)//case 2,which means we cant split ones equally
            return 0;
        //case 3
        long ones=one/3;//number of ones that should be present in each part
        one=0;
        long part1=0;//number of ways in which part1 and part2 can be split
        long part2=0;
        for(int i=0;i<c.length;i++)
        {
            if(c[i]=='1')
                one++;
            if(one==ones)
                part1++;
            if(one==2*ones)
                part2++;
        }
        
        return (int)((part1*part2)%mod);
    }
}
class Solution {
public:
    int MOD = 1e9 + 7 ;
    int numWays(string s) {
        int ones = count(begin(s),end(s),'1') , n = s.size() ;
        if(ones % 3) return 0 ;
        if(!ones) return (((n-1) * 1LL * (n-2) * 1LL) / 2) % MOD ; /// n- 1 C 2
        
        int left = 0 , right = 0 , count = 0 , i = 0 ;
        while(count <= ones / 3){
            count += s[i++] == '1' ;
            if(count == ones/3) ++left ;
        }
        i = n - 1 , count = 0 ;
        while(count <= ones/3){
            count += s[i--] == '1' ;
            if(count == ones/3) ++ right ;
        }
        
        return (left * 1LL * right * 1LL) % MOD ;
    }
};
var numWays = function(s) {
    let one = 0;
    let list = [];
    for(let i = 0; i < s.length; i++){
        if(s[i]==="1") one++, list.push(i);
    }
    if(one%3!==0) return 0;
    if(one===0) return ((s.length-1)*(s.length-2)/2) % 1000000007;
    one/=3;
    return ((list[one]-list[one-1])*(list[2*one]-list[2*one-1])) % 1000000007;
};
Number of Ways to Split a String