Given a binary string s (a string consisting only of '0's and '1's), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).
Return the number of ways s can be split such that the number of characters '1' is the same in s1, s2, and s3.
Since the answer may be too large, return it modulo 10^9 + 7.
 
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"

Example 4:
Input: s = "100100010100110"
Output: 12

 
Constraints:

3 <= s.length <= 10^5
s[i] is '0' or '1'.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def numWays(self, s: str) -> int:
        n = s.count('1')
        if n % 3 != 0: return 0
        if n == 0: return (((len(s) - 1) * (len(s) - 2)) // 2) % (10**9 + 7)
        m = n // 3
        L = s.split('1')
        return ((len(L[m]) + 1) * (len(L[2*m]) + 1)) % (10**9 + 7)
            


class Solution:
    def numWays(self, s: str) -> int:
        tot_ones=s.count('1')
        if tot_ones%3 !=0:
            return 0
        
        c=0
        ln=len(s)
        if tot_ones==0:
            return ((ln-2)*(ln-1)//2)%(10**9+7)
        fe=ss=se=ts=None
        for i,d in enumerate(s):
            if d=='1':
                c+=1
            
            if c==tot_ones//3 and fe is None:
                fe=i
            if c==tot_ones//3+1 and ss is None:
                ss=i
            if c==2*tot_ones//3 and se is None:
                se=i
            if c==2*tot_ones//3+1 and ts is None:
                ts=i
        
        return ((ss-fe)*(ts-se))%(10**9+7)

class Solution:
    def numWays(self, s: str) -> int:
        ones = 0
        zeroes = 0
        for char in s:
            if char == '1':
                ones += 1
            else:
                zeroes += 1
        
        if ones > 0 and ones % 3 != 0:
            return 0
        
        if ones == 0:
            n = len(s) - 3
            res = 1
            diff = 2
            while n:
                res += diff
                diff += 1
                n -= 1
            return res % ((10 ** 9) + 7)
        ones_interval = ones // 3
        
        left, right = 0, 0
        
        i = 0
        temp = 0
        while i < len(s):
            if s[i] == '1':
                temp += 1
            i += 1
            if temp == ones_interval:
                break
        while i < len(s):
            if s[i] == '0':
                left += 1
            if s[i] == '1' or temp == 2 * ones_interval:
                break
            i += 1
        while i < len(s):
            if s[i] == '1':
                temp += 1
            i += 1
            if temp == 2 * ones_interval:
                break
        while i < len(s):
            if s[i] == '0':
                right += 1
            if s[i] == '1':
                break
            i += 1
        if not left:
            return (right+1) % ((10 ** 9) + 7)
        if not right:
            return (left+1) % ((10 ** 9) + 7)
        return ((left+1)*(right+1)) % ((10 ** 9) + 7)


from scipy.special import comb


class Solution:
    def numWays(self, s: str) -> int:
        n = sum(c == '1' for c in s)
        if n % 3:
            return 0
        if n == 0:
            return comb(len(s) - 1, 2, exact=True) % 1000000007
        k = n // 3
        s_iter = iter(s)
        splited = s.split('1')
        return (len(splited[k]) + 1) * (len(splited[2 * k]) + 1) % 1000000007

class Solution:
    def numWays(self, s: str) -> int:
        from math import factorial
        c= s.count('1')
        if c%3 !=0:
            return 0
        if c==0:
            pos= len(s)-1
            numerator= factorial(pos)
            denominator= factorial(2)* factorial(pos-2)
            return int((numerator/ denominator)% ( 10**9 + 7))
            
        num1_each_group= int(c/3)
       
        track=0
        track_g1_l1=0
        track_g2_f1=0
        for i in range(len(s)):
            if s[i]=='1':
                track+=1
            if track== num1_each_group:
                track_g1_l1=i
                break
        track=0
        for i in range(len(s)):
            if s[i]=='1':
                track+=1
               
            if track== num1_each_group+1:
                track_g2_f1=i
                break
        gap1= track_g2_f1- track_g1_l1
        
        track=0
        track_g2_l1=0
        for i in range(len(s)):
            if s[i]=='1':
                track+=1
            if track== num1_each_group*2:
                track_g2_l1=i
                break
                
        track=0
        track_g3_f1=0
        for i in range(len(s)):
            if s[i]=='1':
                track+=1
            if track== num1_each_group*2+1 :
                track_g3_f1=i
                break
        
        gap2=  track_g3_f1- track_g2_l1
        return int(gap1*gap2% (10**9 + 7))
       
                
            
            
                
           
                


class Solution:
    def numWays(self, s: str) -> int:
      res = 0
      c = collections.Counter(s)
      print (c)
      tot = c['1']
      if tot%3: return 0
      mod = 10**9 + 7
      if tot==0:
        n = len(s)-1
        # return (((n%mod)*((n-1)%mod))%mod)//2
        return ((n*(n-1))//2)%mod
        
      
      ctr = 0
      res = 1
      
      eq = tot//3
      a, b, c, d = -1, -1, -1, -1
      for i, ch in enumerate(s):
        
        if ch=='1': ctr += 1
        
        if a<0 and ctr==eq: a = i
        if b<0 and ctr==eq+1: b = i
        if c<0 and ctr==2*eq: c = i
        if d<0 and ctr==2*eq+1: d = i
        
      # print (a, b, c, d)
      return (((b-a)%mod)*((d-c)%mod))%mod

class Solution:
    def numWays(self, s: str) -> int:
        all = s.count('1')
        if all == 0:
            if len(s)%2 ==0:
                c1, c2 = int((len(s)-2)/2), len(s)-1
            else:
                c1, c2 = int((len(s)-1)/2), len(s)-2
            return self.modres(c1, c2)
        if all % 3 !=0:
            return 0
        one = all/3
        c1 = self.check(s, one)
        c2 = self.check(s[::-1], one)

        return self.modres(c1, c2)
    def modres(self, c1, c2):
        mod = pow(10,9)+7
        return ((c1%mod)*(c2%mod))%mod


    def check(self, s, one):
        count = 0
        for i in range(len(s)):
            if s[i]=='1':
                count+=1
                if count == one:
                    p1 = i
                elif count > one:
                    p2 = i
                    break
        return p2-p1


class Solution:
    def numWays(self, s: str) -> int:
        m = 10 ** 9 + 7
        c = Counter(s)
        ones = c['1']
        if ones % 3 != 0:
            return 0
        if ones == 0:
            return comb(len(s)-1,2) % m
        count = 0
        a = 0
        b = 0
        for i in range(len(s)):
            if count == (ones // 3):
                a += 1
            if count == (2*ones // 3):
                b += 1
            if s[i] == '1':
                count += 1
        #print(a,b)
        return (a*b % m)

class Solution:
    def numWays(self, s: str) -> int:
        prefix = [0 for i in range(len(s))]
        for i in range(len(s)):
            if(s[i] == '1'):
                if(i == 0):
                    prefix[i] = 1
                else:
                    prefix[i] = 1 + prefix[i-1]
            else:
                if(i!=0):
                    prefix[i] = prefix[i-1]
        if(prefix[-1] == 0):
            return(((len(s)-2)*(len(s)-1)//2)%(10**9+7))
        elif(prefix[-1]%3!=0):
            return(0)
        else:
            c1 = 0
            c2 = 0
            for i in range(len(prefix)):
                if(prefix[i] == prefix[-1]//3):
                    c1+=1
                elif(prefix[i] == 2*prefix[-1]//3):
                    c2+=1
            return((c1*c2)%(10**9+7))
                


class Solution:
    def numWays(self, s: str) -> int:
        count1s = len([x for x in s if x == '1'])
        if count1s % 3:
            return 0
        if not count1s:
            return ((len(s)-1)*(len(s)-2)//2) % (1000000007)
        idx1 = -1
        idx2 = -1
        idx3 = -1
        idx4 = -1
        ct = 0
        for i, c in enumerate(s):
            if c == '1':
                ct += 1
            if ct == count1s//3 and idx1 == -1:
                idx1 = i
            if ct == (count1s//3)+1 and idx2 == -1:
                idx2 = i
            if ct == 2*(count1s//3) and idx3 == -1:
                idx3 = i
            if ct == 2*(count1s//3)+1 and idx4 == -1:
                idx4 = i
        return (idx2-idx1)*(idx4-idx3) % (1000000007)

class Solution:
    def numWays(self, s: str) -> int:
        M = 10 ** 9 + 7
        
        count = collections.Counter(s)
        print(count)
        cnt = count['1']
        if cnt % 3 != 0: return 0        
        if cnt == 0: return comb(len(s) - 1, 2) % M
        
        
        target = cnt // 3
        left, mid, right = 0, 0, 0
        cur = 0
        
        for i in range(len(s)):
            if s[i] == '1':
                cur+= 1
            if cur == target:
                left += 1
            elif cur == target * 2:
                mid += 1
            
        
        print((left,mid,right))
        return left * mid % M


class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10**9 + 7
        
        total = sum([1 if c == '1' else 0 for c in s])
        if total == 0:
            n = len(s)-1
            return (n * (n-1) // 2) % MOD # nCr combinatorial formula  
        if total % 3 > 0:
            return 0
                
        x = total // 3
        count = 0
        zero1 = 0
        zero2 = 0
        for i,c in enumerate(s):
            if c == '1':
                count += 1
            if c == '0' and count == x:
                zero1 += 1
            elif c == '0'  and count == 2*x:
                zero2 += 1
            
        ans = (zero1+1) * (zero2+1)    
        return ans % MOD

class Solution:
    def numWays(self, s: str) -> int:
        n = sum(1 for i in s if i == '1')
        if n == 0: return ((len(s) - 1) * (len(s) - 2) // 2) % (10 ** 9 + 7)
        if n % 3 != 0: return 0
        f1 = f2 = f3 = f4 = False
        i1 = i2 = i3 = i4 = 0
        k = n // 3
        cur = 0
        for i in range(len(s)):
            if s[i] == '1':
                cur += 1
            if not f1 and cur == k:
                i1 = i
                f1 = True
            if not f2 and cur == k + 1:
                i2 = i
                f2 = True
            if not f3 and cur == 2 * k:
                i3 = i
                f3 = True
            if not f4 and cur == 2 * k + 1:
                i4 = i
                f4 = True
        return ((i2 - i1) * (i4 - i3)) % (10 ** 9 + 7)

class Solution:
    def numWays(self, s: str) -> int:
        total, res, n = 0, 0, len(s)
        for ch in s:
            if ch == '1':
                total += 1
        if total % 3 != 0: return res
        if total == 0: return (math.factorial(n - 1) // math.factorial(n - 3) // 2) % (10**9 + 7)
        l, r, cnt = 0, 0, 0
        for i,ch in enumerate(s):
            if ch == '1': 
                cnt += 1
                if cnt == (total // 3): 
                    l = i
            if cnt == (total // 3) + 1:
                r = i
                break
        res = (r - l) % (10**9 + 7)
        cnt = 0
        for i in range(len(s) - 1, -1, -1):
            ch = s[i]
            if ch == '1': 
                cnt += 1
                if cnt == (total // 3): 
                    r = i
            if cnt == (total // 3) + 1:
                l = i
                break
        res *= (r - l)
        return res % (10**9 + 7)

from math import factorial

class Solution:
    def numWays(self, s: str) -> int:
        count1 = s.count('1')
        if count1 % 3 != 0:
            return 0
        required = s.count('1') // 3
        if not required:
            return (factorial(len(s) - 1) // factorial(len(s) - 3) // 2 )% 1000000007
        
        options = 1
        for loop in range(2):
            current = 0
            for i, ch in enumerate(s):
                if current == required:
                    break
                if ch == '1':
                    current += 1
            for j, ch in enumerate(s[i:], 1):
                if ch == '1':
                    break
            options *= j
            s = s[::-1]

        return options % 1000000007

from math import factorial

class Solution:
    def numWays(self, s: str) -> int:
        ans = 0
        n = len(s)
        xd = s.count('1')
        if s.count('0') == 0:
            if xd % 3 != 0:
                return 0
            return 1
        if xd == 0:
            if n == 3:
                return 1
            n = n - 1
            ans = factorial(n) / factorial(n-2) / factorial(2)
        else:
            if xd % 3 != 0:
                return 0
            x = xd // 3
            ti = [x, x]
            j = 0
            while ti[0] > 0:
                if s[j] == '1':
                    ti[0] -= 1
                j += 1 
            ti[0] = j
            while ti[1] > 0:
                if s[j] == '1':
                    ti[1] -= 1
                j += 1 
            ti[1] = j

            zc = [0, 0]
            j = ti[0]
            while s[j] == '0':
                zc[0] += 1
                j += 1
            j = ti[1]
            while s[j] == '0':
                zc[1] += 1
                j += 1
                
            # print(zc)
            
            lv = 0
            rv = 0
            if zc[0] > 0:
                zc[0] += 1
                lv = factorial(zc[0]) / factorial(zc[0]-1)
            if zc[1] > 0:
                zc[1] += 1
                rv = factorial(zc[1]) / factorial(zc[1]-1)
            
            if max([lv, rv]) == 0:
                return 1
            
            if lv > 0 and rv > 0:
                ans = lv * rv
            else:
                ans = lv + rv
        
        ans = int(ans)
        return ans % (10**9 + 7)

class Solution:
    def numWays(self, s: str) -> int:
        n = s.count('1')
        if n % 3 != 0:
            return 0
        if n == 0:
            return comb(len(s) - 1, 2) % (10**9 + 7)
        a, b, c, d = self.findThirdOneInds(s, n)
        return ((b - a) * (d - c)) % (10**9 + 7)
        
        
    def findThirdOneInds(self, s, n):
        out = []
        ind = -1
        for i in range(2 * n // 3 + 2):
            ind = s.find('1', ind+1)
            if i == n // 3 - 1:
                out.append(ind)
            if i == n // 3:
                out.append(ind)
            if i == 2 * n // 3 - 1:
                out.append(ind)
            if i == 2 * n // 3:
                out.append(ind)
            
        return out

class Solution:
    def numWays(self, s: str) -> int:
        st = collections.Counter(s)
        n = len(s)
        mod = 10**9 + 7
        if st['1'] == 0:
            return (((n-1)*(n-2))//2)%mod
        if st['1']%3:
            return 0
        
        x = st['1']//3
        i = 0
        count = 0
        b1,b2 = 0,0
        while count <= 2*x:
            if s[i] == '1':
                count += 1
                if count == x:
                    b1 += 1
                elif count == 2*x:
                    b2 += 1
            if s[i] == '0' and count == x:
                b1 += 1
            
            if s[i] == '0' and count == 2*x:
                b2 += 1
            i += 1
            
        return (b1*b2)%mod
                
            


class Solution:
    def numWays(self, s: str) -> int:
        k = s.count('1')
        if k % 3:
            return 0
        
        if not '1' in s:
            n = len(s)
            return ((n - 1) * (n - 2) // 2) % (10**9 + 7)
        
        k //= 3
        
        l0 = r0 = l1 = r1 = 1 << 60
        cnt = 0
        for i, c in enumerate(s):
            if c == '1':
                cnt += 1
            if cnt == k:
                l0 = min(l0, i)
            if cnt == k + 1:
                l1 = min(l1, i)
            if cnt == 2 * k:
                r0 = min(r0, i)
            if cnt == 2 * k + 1:
                r1 = min(r1, i)
        
        print(l0, l1, r0, r1)
        return (l1 - l0) * (r1 - r0) % (10**9 + 7)

from math import factorial

class Solution:
    def numWays(self, s: str) -> int:
        ans = 0
        n = len(s)
        xd = s.count('1')
        if s.count('0') == 0:
            if xd % 3 != 0:
                return 0
            return 1
        if xd == 0:
            if n == 3:
                return 1
            n = n - 1
            ans = factorial(n) / factorial(n-2) / factorial(2)
        else:
            if xd % 3 != 0:
                return 0
            x = xd // 3
            ti = [x, x]
            j = 0
            while ti[0] > 0:
                if s[j] == '1':
                    ti[0] -= 1
                j += 1 
            ti[0] = j
            while ti[1] > 0:
                if s[j] == '1':
                    ti[1] -= 1
                j += 1 
            ti[1] = j

            zc = [0, 0]
            j = ti[0]
            while s[j] == '0':
                zc[0] += 1
                j += 1
            j = ti[1]
            while s[j] == '0':
                zc[1] += 1
                j += 1
                
            # print(zc)
            
            lv = 0
            rv = 0
            if zc[0] > 0:
                zc[0] += 1
                lv = factorial(zc[0]) / factorial(zc[0]-1)
            if zc[1] > 0:
                zc[1] += 1
                rv = factorial(zc[1]) / factorial(zc[1]-1)
            
            if max([lv, rv]) == 0:
                return 1
            
            if lv > 0 and rv > 0:
                ans = lv * rv
            else:
                ans = lv + rv
        # print(1)
        ans = int(ans)
        return ans % (10**9 + 7)

class Solution:
    def numWays(self, s: str) -> int:
        ones = 0
        d = {}
        for i in range(len(s)):
            x = s[i]
            if x == '1':
                ones += 1
            d[i] = ones
        if ones %3 != 0:
            return 0
        if ones == 0:
            return (len(s)-1)*(len(s)-2)//2%(10**9+7);
        one = 0
        for i in range(len(s)-2):
            if d[i] * 3 == ones:
                one += 1
            elif d[i] * 3 > ones:
                break
        #print (\"one\", one, i)
        two = 0
        for i in range(i, len(s)-1):
            if (d[i]/2)*3 == ones:
                two += 1
            elif (d[i]/2)*3 > ones:
                break
        #print (\"two\", two)
        return (one*two)%(10**9+7)

class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        
        
        #calculate count
        cnt = 0
        for i in s:
            if i == '1':
                cnt += 1
        if cnt%3 != 0:
            return 0
        
        partn = cnt/3
        
        
        range1_start = n+1
        range1 = [0,n-3]
        first = 0
        last = 0
        #calculate range1
        cnt = 0
        for idx, i in enumerate(s[:n-2]):
            if i == '1':
                cnt += 1
            
            if cnt == partn:
                if first == 0:
                    first = 1
                    range1[0] = idx
                
            if cnt > partn:
                if last == 0:
                    last = 1
                    range1[1] = idx-1
                
        
        #print(range1_low, range1_high)
        
        #calculate range2
        range2 = [range1[0]+1,n-2]
        first = 0
        last = 0
        cnt = 0

        for idx, i in enumerate(s[range2[0]:n]):
            if i == '1':
                cnt += 1
            
            if cnt == partn:
                if first == 0:
                    first = 1
                    range2[0] += idx 
                
            if cnt > partn:
                if last == 0:
                    last = 1
                    range2[1] = range1[0] + idx
                
        
        #print(range2_low, range2_high)
#         print(range1, range2)       
        
        total = 0
        modulo = pow(10,9) + 7
        for i in range(range1[0], range1[1]+1):
            j = range2[0]
            if i<j and i<n and j<n:
                add = (range2[1] - range2[0] + 1)
                total += add%modulo
                #print(add, total)
            else:
                total += (range2[1] - i)%modulo
        # print(total)
        total =  total%modulo
        # print(total)
        return total

class Solution:
    def numWays(self, s: str) -> int:
        all = s.count('1')
        if all == 0:
            if len(s)%2 ==0:
                c1, c2 = int((len(s)-2)/2), len(s)-1
            else:
                c1, c2 = int((len(s)-1)/2), len(s)-2
            return self.modres(c1, c2)
        if all % 3 !=0:
            return 0
        one = all/3
        c1 = self.check(s, one)
        c2 = self.check(s[::-1], one)

        return self.modres(c1, c2)
    def modres(self, c1, c2):
        mod = pow(10,9)+7
        return (c1%mod*c2%mod)%mod


    def check(self, s, one):
        count = 0
        for i in range(len(s)):
            if s[i]=='1':
                count+=1
                if count == one:
                    p1 = i
                elif count > one:
                    p2 = i
                    break
        return p2-p1





class Solution:
    def numWays(self, s: str) -> int:
        ones = 0
        zeroes = 0
        for char in s:
            if char == '1':
                ones += 1
            else:
                zeroes += 1
        
        if ones > 0 and ones % 3 != 0:
            return 0
        
        if ones == 0:
            n = len(s) - 3
            res = 1
            diff = 2
            while n:
                res += diff
                diff += 1
                n -= 1
            return res % ((10 ** 9) + 7)
        ones_interval = ones // 3
        
        left, right = 0, 0
        
        i = 0
        temp = 0
        while i < len(s):
            if s[i] == '1':
                temp += 1
            i += 1
            if temp == ones_interval:
                break
        while i < len(s):
            if s[i] == '0':
                left += 1
            if s[i] == '1' or temp == 2 * ones_interval:
                break
            i += 1
        while i < len(s):
            if s[i] == '1':
                temp += 1
            i += 1
            if temp == 2 * ones_interval:
                break
        while i < len(s):
            if s[i] == '0':
                right += 1
            if s[i] == '1':
                break
            i += 1
        print((left, right))
        if not left:
            return (right+1) % ((10 ** 9) + 7)
        if not right:
            return (left+1) % ((10 ** 9) + 7)
        return ((left+1)*(right+1)) % ((10 ** 9) + 7)


class Solution:
    def numWays(self, s: str) -> int:
        # 000 ==> 1
        # 111 ===> 1
        nums = [0]*len(s)
        cum = 0
        hh = Counter()
        for i in range(len(s)):
            if s[i] == '1':
                cum += 1
            nums[i] = cum
            hh[cum] += 1
        if cum % 3 != 0:
            return 0
        if cum == 0:
            return int(math.comb(hh[0]-1,2))  % (1000000007)
        each = cum//3 
        print((hh, each))
        return int(hh[each]*hh[2*each] % (1000000007))


class Solution:
    def numWays(self, s: str) -> int:
        f = [0,0]
        ind,curr = 0,0
        target = 0
        for i in s: target+=1 if i=='1' else 0
        if target%3:
            return 0
        target = target//3
        n=len(s)
        if target == 0:
            return (math.factorial(n-1)//(math.factorial(2)*math.factorial(n-3)))%(10**9+7)
        for i in range(len(s)):
            if s[i]=='1':
                curr+=1
                if ind==1 or ind==3:
                    ind+=1
            elif ind==1 or ind==3:
                f[(ind-1)//2]+=1
            if curr==target:
                ind+=1
                curr=0
        return ((f[0]+1)*(f[1]+1))%(10**9+7)

class Solution:
    def numWays(self, s: str) -> int:
        n = s.count('1')
        m = 10**9+7
        if n%3 != 0:
            return 0
        if n == 0:
            return comb(len(s)-1,2)%m
        n//=3
        
        k = n
        i = 0
        while k:
            if s[i] == '1':
                k-=1
            i+=1
        x = 1
        while s[i] != '1':
            x+=1
            i+=1
        k = n
        while k:
            if s[i] == '1':
                k-=1
            i+=1
        y = 1
        while s[i] != '1':
            y+=1
            i+=1
        return (y*x)%m

class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        n1 = s.count('1')
        if n1 %3!= 0:
            return 0
        if n1 == 0:
            return int((n - 2) * (n - 1) / 2) % 1000000007
        j = 0
        k = 0
        l = 0
        m = 0
        counter1 = 0
        for i in range(0, n):
            if s[i] == '1':
                counter1 += 1
                if counter1 == n1/3:
                    j = i
                if counter1 == n1 / 3 + 1:
                    k = i
                if counter1 == n1 /3 *2:
                    l = i
                if counter1 == n1 / 3 * 2 + 1:
                    m = i
                    break
        return (k - j ) * (m - l ) % 1000000007
        
            


class Solution:
    def numWays(self, s: str) -> int:
        mod = pow(10, 9) + 7
        cnt = s.count('1')
        if cnt == 0: return (len(s) - 1) * (len(s) - 2) // 2 % mod
        if cnt % 3 != 0: return 0
        ones = []
        for i, x in enumerate(s):
            if x == '1': ones.append(i)
        return (ones[cnt//3] - ones[cnt//3-1]) * (ones[2*cnt//3] - ones[2*cnt//3 - 1]) % mod

class Solution:
    def numWays(self, s: str) -> int:
        mod = 10**9+7
        cnt = s.count('1')
        if cnt == 0: 
            return (len(s)-1) * (len(s)-2) // 2 % mod
        if cnt % 3 != 0: 
            return 0
        ones = []
        for i,x in enumerate(s):
            if x == '1': 
                ones.append(i)
        return (ones[cnt//3] - ones[cnt//3-1]) * (ones[2*cnt//3]- ones[2*cnt//3-1]) % mod


class Solution:
    def numWays(self, s: str) -> int:
        count = 0
        dic = {}
        M = 10**9+7
        n = len(s)
        for i in range(n):
            if s[i]=='1':
                count+=1
                dic[count] = i
        if count%3 != 0:
            return 0
        if count == 0:
            return int((n-1)*(n-2)/2%M)
        
        x = dic[count/3+1]-dic[count/3]
        y = dic[2*count/3+1]-dic[2*count/3]
        
        return x*y%M

class Solution:
    def numWays(self, s: str) -> int:
        d = []
        for ind,val in enumerate(s):
            if val=='1':
                d.append(ind)
                
        n = len(d)
        ndiv = n//3
        if ndiv*3!=n:
            return 0
        
        if n==0:
            n = len(s)
            res = (n-1)*(n-2)>>1
        else:
            res = (d[ndiv]-d[ndiv-1])*(d[2*ndiv]-d[2*ndiv-1])
            
        return res%(1000000007)


class Solution:
    def numWays(self, s: str) -> int:
        n = s.count('1')
        M = 1000000007
        if not n:
            return ((len(s)-2)*(len(s)-1)//2)%M
        if n % 3:
            return 0
        n //= 3
        i = 0
        cnt = 0
        while i < len(s):
            if s[i] == '1':
                cnt += 1
                if cnt == n:
                    break
            i += 1
        j = len(s) - 1
        cnt = 0
        while j >= 0:
            if s[j] == '1':
                cnt += 1
                if cnt == n:
                    break
            j -= 1
        k = i+1
        while k < len(s) and s[k] == '0':
            k += 1
        l = j - 1
        while l > 0 and s[l] == '0':
            l -= 1
        return (j-l)*(k-i)%M

class Solution:
    def numWays(self, s: str) -> int:
        n, ones = len(s), []
        for i, val in enumerate(s):
            if val == '1':
                ones.append(i)
                
        target = len(ones)
        if target == 0:
            return (((n-1)*(n-2)) // 2) % (10**9 + 7)
        
        if target % 3 != 0:
            return 0
        
        c = target // 3
        return ((ones[c]-ones[c-1])*(ones[2*c]-ones[2*c-1])) % (10**9 + 7)
        


class Solution:
    def numWays(self, s: str) -> int:
        mod = 10 ** 9 + 7

        one = s.count('1')
        if one % 3: return 0
        if one == 0: return ((len(s)-1) * (len(s)-2) // 2) % mod

        k = one // 3
        idx_1, idx_2 = k, k + k
        cnt = a = b = 0
        for d in s:
            if d == '1':
                cnt += 1
            if cnt == idx_1: a += 1
            if cnt == idx_2: b += 1
        
        return (a * b) % mod

class Solution:
    def numWays(self, s: str) -> int:
        mod = 10 ** 9 + 7
        c = s.count('1')
        if c % 3 != 0:
            return 0
        if c == 0:
            tot = 0
            for i in range(len(s) - 2):
                tot += len(s) - 2 - i
            return tot % mod
        lsplit = c // 3
        rsplit = lsplit * 2
        lz, rz = 1, 1
        cnt = 0
        for n in s:
            if n == '1':
                cnt += 1
            else:
                if cnt == lsplit:
                    lz += 1
                elif cnt == rsplit:
                    rz += 1
        return (lz * rz) % mod

class Solution:
    def numWays(self, s: str) -> int:
        L, M = len(s), 10 ** 9 + 7
        ones = s.count('1')
        if ones == 0:
            return (L - 1) * (L - 2) // 2 % M
        if ones % 3:
            return 0
        K = ones // 3
        cnt = one_count = two_count = 0
        for c in s:
            if c == '1':
                cnt += 1
            if cnt == K:
                one_count += 1
            elif cnt == K * 2:
                two_count += 1
        
        return (one_count * two_count) % M




class Solution:
    def numWays(self, s: str) -> int:
        L = len(s)
        count = collections.Counter(s)
        if count['0'] == L:
            return (L - 1) * (L - 2) // 2
        if count['1'] % 3:
            return 0
        K = count['1'] // 3
        prefix = [0] * L
        for k, v in enumerate(s):
            prefix[k] = (v == '1') + (prefix[k - 1] if k else 0)
        count1 = collections.Counter(prefix)
        return count1[K] * count1[K * 2] if count1[K * 3] > 0 else 0

    def numWays(self, s: str) -> int:
        L, M = len(s), 10 ** 9 + 7
        ones = s.count('1')
        if ones == 0:
            return (L - 1) * (L - 2) // 2 % M
        if ones % 3:
            return 0
        K = ones // 3
        cnt = one_count = two_count = 0
        for c in s:
            if c == '1':
                cnt += 1
            if cnt == K:
                one_count += 1
            elif cnt == K * 2:
                two_count += 1

        return one_count * two_count % M




class Solution:
    def numWays(self, s: str) -> int:
        one_cnt = 0
        def dfs(s, num, start, left):
            ans = 0
            for i in range(start, len(s)):
                if s[i] == '1':
                    one_cnt += 1
                if one_cnt == num:
                    ans += dfs(s, num, i+1, left-1)
                    ans = ans%(10**9+7)
            return ans
        
        one_cnt = Counter(s)['1']
        if one_cnt%3 != 0:
            return 0
        if one_cnt == 0:
            return ((len(s)-1)*(len(s)-2)//2)%(10**9+7)
        
        num = one_cnt/3
        i = 0
        cnt = 0
        while cnt < num:
            if s[i] == '1':
                cnt += 1
            i += 1
        start = i
        while i < len(s) and s[i] == '0':
            i += 1
        first = i - start + 1
        
        cnt2 = 0
        while cnt2 < num:
            if s[i] == '1':
                cnt2 += 1
            i += 1
        start2 = i
        while i < len(s) and s[i] == '0':
            i += 1
        second = i - start2 + 1
        
        ans = (first*second)%(10**9+7)
        return ans


class Solution:
    def numWays(self, s: str) -> int:
        modv = 10**9+7
        countOne = 0
        for x in s:
            if x == '1':
                countOne += 1
        if countOne == 0:
            return (len(s)-2)*(len(s)-1)//2%modv
        if countOne%3 !=0:
            return 0
        count = 0
        indexOfOne = []
        markIndexWhen = [countOne//3, countOne//3+1, countOne//3*2, countOne//3*2+1]
        for i in range(len(s)):
            if s[i] == '1':
                count += 1
                if count in markIndexWhen:
                    indexOfOne.append(i)
        return (indexOfOne[1]-indexOfOne[0])*(indexOfOne[-1] - indexOfOne[-2])%modv

class Solution:
    def numWays(self, s: str) -> int:
        ones_count=s.count('1')
        n=len(s)
        if ones_count==0:
            return (((n-2)*(n-1))//2)%(10**9+7)
        if ones_count%3!=0:
            return 0
        no_of_ones=ones_count/3
        count,count_1st,count_2nd=0,0,0
        for i in s:
            if i=='1':
                count+=1
            if count==no_of_ones:
                count_1st+=1
            if count==2*no_of_ones:
                count_2nd+=1
        return (count_1st*count_2nd)%(10**9+7)

class Solution:
    def numWays(self, s: str) -> int:
        ones = s.count('1')
        if ones % 3: return 0
        if ones == 0:
            return ((len(s)-1)*(len(s)-2)//2)%1000000007
        ones //= 3
        c = 0
        F, S = 0, 0
        for i, x in enumerate(s):
            if x == '1':
                c += 1
            if c == ones and x == '0':
                F += 1
            elif c == 2 * ones and x == '0':
                S += 1
        return ((F+1)*(S+1))%1000000007


class Solution:
    def numWays(self, s: str) -> int:
        count = s.count('1')
        
        if count % 3 != 0:
            return 0
        
        length = len(s) - 1
        if count == 0:
            return (( length ) * ( length - 1 ) // 2) % 1000000007
        
        first_range, second_range, index, curr_ones, per_triplet = 1, 1, 0, 0, count // 3
        
        while index < length:
            if curr_ones > 2 * per_triplet:
                break
            
            if s[index] == '1':
                curr_ones += 1
            elif curr_ones == per_triplet:
                first_range += 1
            elif curr_ones == 2 * per_triplet:
                second_range += 1
            
            index += 1

        return (first_range * second_range) % 1000000007

class Solution:
    # 300 ms 29.38%. Time and Space: O(N)
    def numWays(self, s: str) -> int:
        ones = sum(c == '1' for c in s)
        
        if ones % 3: return 0
        
        if ones == 0:
            N = len(s) - 2
            return N * (N + 1) // 2 % (10**9 + 7)
        
        target = ones // 3
        
        N = len(s)
        
        left1 = left2 = None
        cnt = 0
        for i, c in enumerate(s):
            if c == '1':
                cnt += 1
            if cnt == target:
                if left1 is None:
                    left1 = i
                left2 = i
        
        right1 = right2 = None
        cnt = 0
        for i, c in enumerate(s[::-1]):
            if c == '1':
                cnt += 1
            if cnt == target:
                if right1 is None:
                    right1 = N - 1 - i
                right2 = N - 1 - i
        ans = (left2 - left1 + 1) * (right1 - right2 + 1) 
        return ans % (10**9 + 7)
    
    def numWays(self, s: str) -> int:
        ones = sum(c == '1' for c in s)
        
        if ones % 3: return 0
        if ones == 0:
            N = len(s) - 2
            return N * (N + 1) // 2 % (10**9 + 7)
        
        target = ones // 3
        indexes = [i for i, c in enumerate(s) if c == '1']
        ans = (indexes[target] - indexes[target - 1]) * (indexes[-target] - indexes[~target])
        return ans % (10**9 + 7)
            


class Solution:
    def numWays(self, s: str) -> int:
        ttt = 10**9+7
        zs = list(map(len, s.split('1')))
        
        if not (len(zs)-1) % 3 == 0 :
            return 0
        if len(zs) == 1 :
            return (len(s)-1)*(len(s)-2)//2 % ttt
        ps = len(zs)//3
        return (zs[ps]+1)*(zs[ps*2]+1)% ttt

class Solution:
    def numWays(self, s: str) -> int:
        count = s.count('1')
        
        if count % 3 != 0:
            return 0
        
        length = len(s) - 1
        if count == 0:
            return (( length ) * ( length - 1 ) // 2) % 1000000007
        
        first_range, second_range, index, curr_ones, per_triplet = 1, 1, 0, 0, count // 3
        
        while index < length:
            if s[index] == '1':
                curr_ones += 1
            elif curr_ones == per_triplet:
                first_range += 1
            elif curr_ones == 2 * per_triplet:
                second_range += 1
            
            index += 1

        return (first_range * second_range) % 1000000007

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        n = sum(1 for c in s if c == '1')
        if n % 3 != 0:
            return 0
        if n == 0:
            t = (len(s) - 1) * (len(s) - 2) // 2
            return t % MOD
        n //= 3
        
        def f(s, n):
            i = 0
            while n:
                n -= 1 if s[i] == '1' else 0
                i += 1
            k = 1
            while s[i] == '0':
                k += 1
                i += 1
            return k
        
        return f(s, n) * f(''.join(reversed(s)), n) % MOD

class Solution:
    def numWays(self, s: str) -> int:
        ones = s.count('1')
        if ones%3!=0:
            return 0
        n = len(s)
        mod = 10**9+7
        if ones==0:
            return (n-1)*(n-2)//2%mod
        count = 0
        first_count = 0
        second_count = 0
        for cha in s:
            if cha == '1':
                count += 1
            if count == ones//3:
                first_count+=1
            elif count == ones//3*2:
                second_count+=1
        return first_count*second_count%mod

class Solution:
    def numWays(self, s: str) -> int:
        
        def nice_multiply(a, b, mod):
            
            (a / 8) 
        
        def get_total_ones():
            
            result = 0
            
            for binary in s:
                if binary == '1':
                    result += 1
            
            return result
        
        total_ones = get_total_ones()
        
        if total_ones == 0:
            
            return int((len(s) - 1) * (len(s) - 2) / 2) % 1000000007
        
        if total_ones % 3 != 0:
            return 0
        
        first_cut_numbers = 0
        second_cut_numbers = 0
        
        cut_amount = total_ones / 3
        
        current_ones = 0
        
        for binary in s:
            
            if binary == '1':
                current_ones += 1
            
            if current_ones == cut_amount:
                first_cut_numbers += 1
            
            if current_ones == 2 * cut_amount:
                second_cut_numbers += 1
        
        return (first_cut_numbers * second_cut_numbers) % 1000000007

class Solution:
    def numWays(self, s: str) -> int:
        count_map = collections.Counter(s)
        if count_map['1']%3!=0:
            return 0
        else:
            if count_map['1']==0:
                if count_map['0']<3:
                    return 0
                
                if count_map['0']==3:
                    return 1
                
                i = 4
                res = 1
                while i<=count_map['0']:
                    res += i-2
                    i+=1
                return res%1000000007
                    
            else:
                i = 0
                one_count = 0
                s1_start, s1_end, s2_start, s2_end = -1,-1,-1,-1
                factor = count_map['1']//3
                while i<len(s):                    
                    if s[i]=='1':
                        one_count+=1
                        if one_count==factor:
                            s1_start = i
                        elif one_count==(factor+1):
                            s1_end = i
                        
                        if one_count==(factor*2):
                            s2_start = i
                        elif one_count==(factor*2+1):
                            s2_end = i
                            break
                    i+=1
                return ((s1_end-s1_start)*(s2_end-s2_start))%1000000007


class Solution:
    def numWays(self, s: str) -> int:
        totalones = 0
        for i in range(len(s)):
            if s[i] == '1':
                totalones+=1
        
        if totalones%3 != 0:
            return 0
        if totalones == 0:
            return ((len(s) - 2)*(len(s) - 1)//2) % (10**9 + 7)
        onesEachPart, waysFirstPart, waysSecondPart = totalones//3, 0, 0
        count = i = 0
        while count <= 2*onesEachPart:
            if s[i] == '1':
                count+=1
            if count == onesEachPart:
                waysFirstPart+=1
            elif count == 2*onesEachPart:
                waysSecondPart+=1
            i+=1
        
        return (waysFirstPart * waysSecondPart) % (10**9 + 7)
                
            


from math import comb
class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        k = s.count('1')
        if k%3:
            return 0
        if k == 0:
            return comb(n-1, 2) % (10**9 + 7)
        third = k // 3
        start=-1
        for i in range(third):
            start = s.find('1', start+1)
        first_last = start
        for i in range(third):
            start = s.find('1', start+1)
        second_last = start
        first_zeros = s.count('0', first_last, s.find('1', first_last+1))
        second_zeros = s.count('0', second_last, s.find('1', second_last+1))
        return ((first_zeros+1)*(second_zeros+1))% (10**9 + 7)
        
            


class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        count = 0
        cur = 0
        mod = 1000000007
        for i in range(len(s)):
            if s[i] == '1':
                cur +=1
            
        if cur == 0:
            return (((n-1)*(n-2))//2)%mod
        
        left = 0 
        lc = 0
        for i in range(n):
            if s[i] == '1':
                left+=1
            if left == cur/3:
                lc += 1
            if left > cur/3:
                break
        right = 0
        rc = 0
        for i in range(n-1,-1,-1):
            if s[i] == '1':
                right+=1
            if right == cur/3:
                rc += 1
            if right > cur/3:
                break
        return (lc*rc)%mod


from math import comb

class Solution:
    def numWays(self, s: str) -> int:
        ones = 0
        for c in s:
            if c == '1':
                ones += 1
        if ones == 0:
            return comb(len(s) - 1, 2) % (10**9 + 7)
        
        if ones % 3 != 0:
            return 0
        
        i = 0
        found = 0
        a = None
        while i < len(s):
            c = s[i]
            if c == '1':
                found += 1
            if found == (ones//3):
                count = 0
                i += 1
                c = s[i]
                while c == '0':
                    count += 1
                    i += 1
                    c = s[i]
                if not a:
                    a = count + 1
                    i -= 1
                else:
                    return (a * (count + 1)) % (10**9 + 7)
                found = 0
            i += 1

class Solution:
    def numWays(self, s: str) -> int:
        one, n, m = s.count('1'), len(s), 10**9 + 7
        # special case: first one for left -> n-2, first two for left -> n-3, ..., 2, 1
        # -> (n-2) + (n-3) + ... + 2 + 1 -> (n-1) * (n-2) // 2
        if not one: return (n - 1) * (n - 2) // 2 % m
        if one % 3: return 0
        curr = l = r = 0
        for c in s:
            curr += c == '1'
            l += curr == (one // 3)
            r += curr == (2 * one // 3)
        
        return l * r % m

class Solution:
    def numWays(self, s: str) -> int:
        c = s.count('1')
        if c%3: return 0
        M = 10**9 +7
        if not c:
            return (len(s)-1)*(len(s)-2)//2%M
    
        cur = 0
        first = 0
        second = 0
        for l in s:
            if cur == c//3:
                first += 1
            elif cur == c//3*2:
                second += 1
            cur += l == '1'
            
        return first*second%M


class Solution:
    def numWays(self, s: str) -> int:        
        k = s.count('1')
        if k % 3 != 0: return 0
        n, M = len(s), 10**9 + 7
        if k == 0: return (n-1)*(n-2)//2 % M
        ans, cnt, i = 1, 0, 0         
        while i < len(s):            
            cnt += s[i] == '1'
            if cnt in [k//3, 2*k//3]:
                j = i+1
                while j < len(s) and s[j] == '0': j += 1
                ans *= j-i
                i = j            
            else: i += 1
            if cnt == 2*k//3: break
        return ans % M
                
                


import collections

class Solution:
    def numWays(self, s):
        count = collections.Counter(s)
        if count['1'] == 0:
            return (len(s) - 1) * (len(s) - 2) // 2 % (10**9 + 7)
        
        if count['1'] < 3 or count['1'] % 3 != 0:
            return 0
        
        ans = 1
        cur = 0
        expand = 1
        find = count['1'] // 3
        slot = 0
        
        for ss in s:
            if slot == 2:
                return ans * expand

            if find > cur:
                # collecting 1
                if ss == '1':
                    cur += 1
            else:
                # collecting 0
                # set to next slot if encounter 1
                if ss == '0':
                    expand += 1
                else:
                    ans *= expand
                    expand = 1
                    cur = 1
                    slot += 1
                    
        ans *= expand
        return ans % (10**9 + 7)

class Solution:
    def numWays(self, s: str) -> int:
        n = s.count('1')
        if n%3!=0:
            return 0
        n = int(n/3)
        if n==0:
            ans = 0
            for i in range(1,len(s)-1):
                ans += len(s)-1-i
            return ans%(10**9 + 7)
        else:
            a = s.split('1')
            return (len(a[n])+1) * (len(a[2*n])+1)%(10**9 + 7)


# 2:52 if num ones % 3 != 0 can't be done
# identify groups, find 0s between them
# 1 00 1 00 1
# |00, 0|0, 00|
# 1 n 1 m 1
# (n + 1)*(m + 1)
# 0 0000 0 -> |0000 (|000, 0|00, 00|0, 000|), 0|000, 00|00, 000|0, 0000|
# 0 000 0 -> |0|00, |00|0, |000|, 0|0|0, 0|00|, 00|0|
class Solution:
    def numWays(self, s: str) -> int:
        count = len(list([char for char in s if char == '1']))
        if count % 3 != 0:
            return 0
    
        if count / 3 == 0:
            zeroes_in_middle = len(s) - 2
            total = 0
            for marker in range(zeroes_in_middle + 1):
                total += (zeroes_in_middle - marker) % (10**9 + 7)
            return total % (10**9 + 7)
        
        def get_zeroes(s, count):
            num_ones = 0
            zeroes = {'first': 0, 'second': 0}
            for bit in s:
                if bit == '1':
                    num_ones += 1
                else:
                    if num_ones == count:
                        zeroes['first'] += 1
                    elif num_ones == 2*count:
                        zeroes['second'] += 1
            return zeroes
                    
        
        zeroes = get_zeroes(s, count / 3)
        
        # print(zeroes)
        
        if not zeroes['first'] and not zeroes['second']:
            return 1
        elif zeroes['first'] and not zeroes['second']:
            return zeroes['first'] + 1
        elif zeroes['second'] and not zeroes['first']:
            return zeroes['second'] + 1
        
        return (zeroes['first'] + 1)*(zeroes['second'] + 1) % (10**9 + 7)


class Solution:
    def numWays(self, s: str) -> int:
        md = 10**9 + 7
        res = 0
        n = len(s)
        n1 = sum(map(lambda x1: 1 if x1 == '1' else 0, s))
        if n > 2 and n1 % 3 == 0:
            x = n1 // 3
            x2 = x << 1
            if x == 0:
                res = (n - 1) * (n - 2) // 2
            else:
                cnt,c1,c2 = 0,0,0
                for i,c in enumerate(s):
                    if c == '1':
                        cnt += 1
                    if cnt == x:
                        c1 += 1
                    elif cnt == x2:
                        c2 += 1
                res = c1 * c2
        return res % md

class Solution:
    def numWays(self, s: str) -> int:
        N, ones = len(s), 0
        for c in s:
            ones += 1 if c == '1' else 0
        
        if ones % 3 == 1:
            return 0
        
        if ones == 0:
            return (((N-1) * (N-2)) >> 1) % (10**9 + 7)
        
        want = ones // 3
        c1, c2 = 0, 0
        p, suff = 0, 0
        for c in s:
            if c == '1': c1 += 1
            if c1 == want:
                p += 1
        
        for c in reversed(s):
            if c == '1': c2+=1
            if c2==want:
                suff+=1
        
        return (p * suff) % (10**9 + 7)
        


class Solution:
    def numWays(self, s: str) -> int:
        ones = sum(c == '1' for c in s)
        if ones % 3:
            return 0
        if ones == 0:
            N = len(s) - 2
            return N * (N + 1) // 2 % (10**9 + 7)
        
        target = ones // 3
        
        N = len(s)
        
        left1 = left2 = None
        cnt = 0
        for i, c in enumerate(s):
            if c == '1':
                cnt += 1
            if cnt == target:
                if left1 is None:
                    left1 = i
                left2 = i
        
        right1 = right2 = None
        cnt = 0
        for i, c in enumerate(s[::-1]):
            if c == '1':
                cnt += 1
            if cnt == target:
                if right1 is None:
                    right1 = N - 1 - i
                right2 = N - 1 - i
        ans = (left2 - left1 + 1) * (right1 - right2 + 1) 
        return ans % (10**9 + 7)
            


class Solution:

    def numWays(self, s: str) -> int:
        L, M = len(s), 10 ** 9 + 7
        ones = s.count('1')
        if ones == 0:
            return (L - 1) * (L - 2) // 2 % M
        if ones % 3:
            return 0
        K = ones // 3
        cnt = one_count = two_count = 0
        for c in s:
            if c == '1':
                cnt += 1
            if cnt == K:
                one_count += 1
            elif cnt == K * 2:
                two_count += 1

        return one_count * two_count % M

    def numWays(self, s: str) -> int:
        L, M = len(s), 10**9+7
        count = collections.Counter(s)
        if count['0'] == L:
            return (L - 1) * (L - 2) // 2 % M
        if count['1'] % 3:
            return 0
        K = count['1'] // 3
        prefix = [0] * L
        for k, v in enumerate(s):
            prefix[k] = (v == '1') + (prefix[k - 1] if k else 0)
        count1 = collections.Counter(prefix)
        return count1[K] * count1[K * 2] % M



def findall(p, s):
    '''Yields all the positions of
    the pattern p in the string s.'''
    i = s.find(p)
    while i != -1:
        yield i
        i = s.find(p, i+1)

def choose(n, k):
    c = 1
    if k > n // 2:
        k = n - k
    for i in range(1, k + 1):
        c = c * (n - i + 1) // i
    return c

def modulo(n):
    return n % (10 ** 9 + 7)

class Solution:
    
    def numWays(self, s: str) -> int:
        n = len(s)
        c = s.count('1')
        if c % 3 != 0:
            return 0
        cp = c // 3 # count in each part
        if cp == 0:
            #special case, no 1, chosse 2 separators in the (n-1) possible spaces
            return modulo(choose(n - 1, 2))
        # find the size n1 of the substring between (cp+1)-th and cp-th occurrances of 1,
        # and the size n2 of the subsring betwwen (cp*2+1)-th and (cp*2)-th occurrances of 1
        indices = list(findall('1', s))
        n1 = indices[cp] - indices[cp - 1] - 1
        n2 = indices[cp*2] - indices[cp*2 - 1] - 1
        # find one separater in (n1 + 1) possible spaces, 
        # and one separater in (n2 + 1) possible spaces 
        result = 0
        if n1 == 0:
            result = n2 + 1
        elif n2 == 0:
            result = n1 + 1
        else:
            result = (n1 + 1) * (n2 + 1)
        return(modulo(result))


class Solution:
    CONST = 10**9 + 7
    def numWays(self, s: str) -> int:
        n = len(s)
        num_ones = 0
        for c in s:
            if c == '1':
                num_ones += 1
        if num_ones % 3 != 0:
            return 0
        if num_ones == 0:
            return ((n-1) * (n-2) // 2)  % self.CONST
        
        first, second = 0, 0
        num_ones_sofar, cutoff = 0, num_ones // 3
        # print(cutoff)
        for i in range(n):
            num_ones_sofar += s[i] == '1'
            if num_ones_sofar < cutoff:
                pass
            elif cutoff <= num_ones_sofar < cutoff + 1:
                first += 1
            elif 2 * cutoff <= num_ones_sofar < 2 * cutoff + 1:
                second += 1  
            else:
                pass
            # print(first, second)
        return (first * second) % self.CONST
                
            
            


class Solution:
    
    # from collections import Counter
    
    CONST = 1_000_000_000 + 7
    
    def numWays(self, s: str) -> int:
        n = len(s)
        # edge cases 
        num_ones = 0
        for c in s:
            if c == '1':
                num_ones += 1        
        if num_ones % 3 != 0:
            return 0
        if num_ones == 0:
            return ((n-1) * (n-2) // 2) % self.CONST
        
        # general case 
        # \"100100010100110\"
        # 1001| 00010100110
        # 10010| 0010100110        
        # 100100| 010100110 
        # 1001000| 10100110
        
        # 0 0
        # 0 0
        # 0 0
        # 1 0
        # 2 0
        # 3 0
        # 4 0
        # 4 1
        # 4 2
        # 4 2
        # 4 2
        # 4 2
        # 4 2
        # 4 2
        # 4 2
        
        num_ones_per_chunk = num_ones // 3
        first, second = 0, 0
        num_ones_sofar = 0
        
        # dumb version
        for idx, c in enumerate(s):
            num_ones_sofar += c == '1'
            if num_ones_sofar < num_ones_per_chunk:
                pass
            elif num_ones_per_chunk <= num_ones_sofar < num_ones_per_chunk + 1:
                first += 1
            elif 2 * num_ones_per_chunk <= num_ones_sofar < 2 * num_ones_per_chunk + 1:
                second += 1
            else:
                pass
            # print(s[:idx+1])
            # print(first, second)
            # print('')
            
        # # smart version
        # for c in s:
        #     num_ones_sofar += c == '1'
        #     if num_ones_sofar == num_ones_per_chunk:
        #         first += 1
        #     elif num_ones_sofar == 2 * num_ones_per_chunk:
        #         second += 1
        
        # \"10101\"
        # \"1001\"
        # \"000000\"
        return (first * second) % self.CONST
            
            


class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        mod = 10 ** 9 + 7
        nums1 = sum(1 if s[i] == '1' else 0 for i in range(n))
        if nums1 % 3 != 0:
            return 0
        num_per = nums1 // 3
        if num_per == 0:
            res = 0
            for i in range(1, n - 1):
                res = (res + (n - 1 - i)) % mod
            return res
        def find_end(start, num1):
            count = 0
            index = start
            while index < n and count < num1:
                if s[index] == '1':
                    count += 1
                index += 1
            return index - 1
        end1 = find_end(0, num_per)
        i = end1 + 1
        while s[i] != '1':
            i += 1
        end2 = find_end(i, num_per)
        j = end2 + 1
        while s[j] != '1':
            j += 1
        return ((i - end1) * (j - end2)) % mod


from functools import reduce, lru_cache


class Solution:
    def numWays(self, arr: str) -> int:
        arr = list(arr)
        count = reduce((lambda accu, element: accu +
                        (1 if element == '1' else 0)), arr, 0)
        if count % 3 != 0:
            return 0
        if count == 0:
            return ((len(arr) - 1) * (len(arr) - 2) >> 1) % (10**9 + 7)

        target = count / 3

        accu = 0
        ways_of_first_cut = 0
        ways_of_second_cut = 0
        for c in arr:
            if c == '1':
                accu += 1
            if accu == target:
                ways_of_first_cut += 1
            elif accu == target * 2:
                ways_of_second_cut += 1

        return (ways_of_first_cut * ways_of_second_cut) % (10**9 + 7)


class Solution:
    def numWays(self, s: str) -> int:
        l = len(s)
        total_cnt = 0
        for i in range(l):
            if s[i] == '1':
                total_cnt += 1
        if total_cnt % 3:
            return 0
        
        cnt = total_cnt // 3
        if total_cnt == 0:
            return ((len(s) - 1) * (len(s) - 2) // 2) % (10**9 + 7)
        
        c1, c2 = 1, 1
        s1, s2 = s, s[::-1]
        idx = 0
        i1 = self.findIdx(s1, cnt)
        i2 = self.findIdx(s2, cnt)
        
        while s1[i1] != '1':
            c1 += 1
            i1 += 1
        while s2[i2] != '1':
            c2 += 1
            i2 += 1
        return c1 * c2 % (10**9 + 7)
        

    def findIdx(self, s, cnt):
        c, idx = 0, 0
        while idx < len(s) and c < cnt:
            if s[idx] == '1':
                c += 1
            idx += 1
        
        return idx
    
            
    


class Solution:
    def numWays(self, s: str) -> int:
        cnt=0
        ans=0
        n=len(s)
        m=1000000007
        for i in range(len(s)):
            if(s[i]=='1'):
                cnt+=1
        if(cnt==0):
            ans=((n-1)*(n-2))/2
            ans=ans%m
            return int(ans)
        else:
            hm=dict()
            cnt=0
            ans=0
            for i in range(len(s)):
                if(s[i]=='1'):
                    cnt+=1
                if cnt not in hm.keys():
                    hm[cnt]=1
                else:
                    hm[cnt]=hm[cnt]+1
            if(cnt%3!=0):
                return 0
            else:
                first=hm[cnt/3]
                tthird=(cnt/3)*2
                second=hm[tthird]
                ans=((first%m)*(second%m))%m         
            return int(ans)

class Solution:
    def numWays(self, s: str) -> int:
        l = len(s)
        total_cnt = 0
        for i in range(l):
            if s[i] == '1':
                total_cnt += 1
        if total_cnt % 3:
            return 0
        
        cnt = total_cnt // 3
        if total_cnt == 0:
            return ((len(s) - 1) * (len(s) - 2) // 2) % (10**9 + 7)
        
        c1, c2 = 1, 1
        s1, s2 = s, s[::-1]
        idx = 0
        i1 = self.findIdx(s1, cnt)
        i2 = self.findIdx(s2, cnt)
        
        while s1[i1] != '1':
            c1 += 1
            i1 += 1
        while s2[i2] != '1':
            c2 += 1
            i2 += 1
        return (c1 * c2) % (10**9 + 7)
        

    def findIdx(self, s, cnt):
        c, idx = 0, 0
        while idx < len(s) and c < cnt:
            if s[idx] == '1':
                c += 1
            idx += 1
        
        return idx
    
            
    


class Solution:
    def numWays(self, s: str) -> int:
        if not s or len(s) < 3 or s.count('1') % 3 != 0:
            return 0
        
        mod = pow(10, 9) + 7
        n = s.count('1')
        if n == 0:
            return (len(s) - 1) * (len(s) - 2) // 2 % mod
        
        c1, c2, i = 0, 0, 0
        for ch in s:
            if ch == '1':
                i += 1
            elif ch == '0' and n / 3 <= i < n / 3 + 1:
                c1 += 1
            elif ch == '0' and n*2 / 3 <= i < n*2 / 3 + 1:
                c2 += 1
        return (c1 + 1) * (c2 + 1) % mod

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        ones = 0
        for c in s:
            ones += 1 if c == '1' else 0
        n = len(s)
        
        if ones % 3 != 0:
            return 0
        if ones == 0:
            return ((n - 2) * (n - 1) // 2) % MOD
        
        ones = ones // 3
        firstLeft = firstRight = - 1
        secondLeft = secondRight = -1
        count = 0
        for i in range(n):
            if s[i] == '1':
                count += 1
                
            if count == ones and firstLeft == -1:
                firstLeft = i
            if count == ones + 1 and firstRight == -1:
                firstRight = i
                
            if count == 2 * ones and secondLeft == -1:
                secondLeft = i
            if count == 2 * ones + 1 and secondRight == -1:
                secondRight = i
        
        return ((firstRight - firstLeft) * (secondRight - secondLeft)) % MOD

import math
class Solution:
    def numWays(self, s: str) -> int:
        dict1 = dict()
        cur = 0
        for i in range(len(s)):
            if(s[i] == '1'):
                dict1[cur+1] = i
                cur += 1
        if(cur%3 != 0):
            return 0
        if(cur == 0):
            len_s = len(s)-1
            return (math.factorial(len_s)//(math.factorial(len_s-2)*math.factorial(2)))%(10**9 + 7)
        
        div = cur//3
        return ((dict1[div+1] - dict1[div])*(dict1[div*2 + 1] - dict1[div*2]))%(10**9 + 7)

class Solution:
    def numWays(self, s: str) -> int:
        cnt = s.count('1')
        if cnt % 3 != 0:
            return 0
        if cnt == 0:
            ans = 0
            for i in range(1, len(s) - 1):
                ans += i
            return ans % (10**9 + 7)
        
        l = r = 1
        c = 0
        
        for i, n in enumerate(s):
            c += 1 if n == '1' else 0
            
            if  c == cnt / 3 and n == '0':
                l += 1
            elif c == (cnt / 3) * 2 and n == '0':
                r += 1
        
        print((l, r))
        return l * r % (10**9 + 7)



class Solution:
    
    import math
    
    def C(self, N,r):
        return int(math.factorial(N)/(math.factorial(r)*math.factorial(N-r)))
    
    def numWays(self, s: str) -> int:
        counter=s.count('1')
        if counter%3!=0:
            return 0
        if counter==0:
            return self.C(len(s)-1, 2) % (10**9+7) 
        
        
        index=[]
        cnt=0
        for ind,char in enumerate(s):
            if char=='1':
                cnt+=1
                if cnt==counter//3:
                    index.append(ind)
                    
                if cnt==(counter//3)+1:
                    index.append(ind)
                    
                if cnt==(2*counter//3):
                    index.append(ind)
                    
                if cnt==(2*counter//3)+1:
                    index.append(ind)
  
        m=index[1]-index[0]
        n=index[3]-index[2]
        return m*n % (10**9+7)