<p>Given a binary string <code>s</code>, you can split <code>s</code> into 3 <strong>non-empty</strong> strings <code>s1</code>, <code>s2</code>, and <code>s3</code> where <code>s1 + s2 + s3 = s</code>.</p>

<p>Return the number of ways <code>s</code> can be split such that the number of ones is the same in <code>s1</code>, <code>s2</code>, and <code>s3</code>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;10101&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are four ways to split s in 3 parts where each part contain the same number of letters &#39;1&#39;.
&quot;1|010|1&quot;
&quot;1|01|01&quot;
&quot;10|10|1&quot;
&quot;10|1|01&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1001&quot;
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;0000&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three ways to split s in 3 parts.
&quot;0|0|00&quot;
&quot;0|00|0&quot;
&quot;00|0|0&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        
        # Step 1: Count the total number of '1's in the string
        one_count = s.count('1')
        
        # If the total count of '1's is not divisible by 3, return 0
        if one_count % 3 != 0:
            return 0
        
        # If the total count of '1's is 0, calculate the number of ways to split the string
        if one_count == 0:
            n = len(s)
            return ((n - 1) * (n - 2) // 2) % MOD
        
        # Step 2: Find the positions of the '1's
        one_positions = [i for i, bit in enumerate(s) if bit == '1']
        n = len(one_positions)
        
        # Step 3: Calculate the number of valid splits
        segment_size = one_count // 3
        first_cut = one_positions[segment_size - 1]
        second_cut = one_positions[2 * segment_size - 1]
        
        # Number of positions to place the first cut
        ways_first_cut = one_positions[segment_size] - first_cut
        # Number of positions to place the second cut
        ways_second_cut = one_positions[2 * segment_size] - second_cut
        
        # Total number of ways to split the string
        return (ways_first_cut * ways_second_cut) % MOD

# Example usage:
solution = Solution()
print(solution.numWays("10101"))  # Output: 4
print(solution.numWays("1001"))   # Output: 0
print(solution.numWays("0000"))   # Output: 3
17800