<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:
        u = [int(i) for i in s]
        count = 0
        n = len(u) -1
        for i in u:
            if i == 1:
                count += 1

        if count % 3 != 0:
            return 0

        if count == 0:
            return ((n * (n-1))//2) % ((10**9) + 7)

        target = count //3
        count1 = 0
        count0 = 0
        ans = 1
        flag = False
        for i in u:
            if i == 1:
                count1 += 1

            if i == 0 and count1 == target:
                count0 += 1

            if count1 > target:
                ans *= (count0+1)
                count0= 0
                count1 = 1
            
        return ans % ((10**9) + 7)









        
    #     return self.dfs(0, 0, target, u)

    # def dfs(self, i, count_1, target, u):
    #     if i == len(u):
    #         return 1

    #     ans = 0
    #     if u[i] == 1:
    #         count_1 += 1
    #         if count_1 == target:
    #             ans += self.dfs(i+1, 0, target, u) + self.dfs(i+1, count_1, target, u)
    #         elif count_1 > target:
    #             ans += self.dfs(i+1, 1, target, u)
    #     else:
    #         ans += self.dfs(i+1, count_1, target, u)
    #     # print(i, ans)
    #     return ans

        
18900