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'.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Mathematics

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 * (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
		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
		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]
			elif 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
		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
			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)


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
		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
		return one * two % (10 ** 9 + 7)


class Solution:

	def numWays(self, s: str) -> int:
		n = len(s)
		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
		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
		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
		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
			else:
				total += (range2[1] - i) % modulo
		total = total % modulo
		return total


class Solution:

	def numWays(self, s: str) -> int:
		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:
		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
			elif 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:

	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:
		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
		elif 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)
		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:
				if ss == '1':
					cur += 1
			elif 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)


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
				elif num_ones == count:
					zeroes['first'] += 1
				elif num_ones == 2 * count:
					zeroes['second'] += 1
			return zeroes
		zeroes = get_zeroes(s, count / 3)
		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)


def findall(p, 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
		if cp == 0:
			return modulo(choose(n - 1, 2))
		indices = list(findall('1', s))
		n1 = indices[cp] - indices[cp - 1] - 1
		n2 = indices[cp * 2] - indices[cp * 2 - 1] - 1
		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)
		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
		return first * second % self.CONST


class Solution:
	CONST = 1000000000 + 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
		num_ones_per_chunk = num_ones // 3
		(first, second) = (0, 0)
		num_ones_sofar = 0
		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
		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:
		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)