Let S be the concatenation of 10^{10} copies of the string 110. (For reference, the concatenation of 3 copies of 110 is 110110110.)
We have a string T of length N.
Find the number of times T occurs in S as a contiguous substring.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - T is a string of length N consisting of 0 and 1.

-----Input-----
Input is given from Standard Input in the following format:
N
T

-----Output-----
Print the number of times T occurs in S as a contiguous substring.

-----Sample Input-----
4
1011

-----Sample Output-----
9999999999

S is so long, so let us instead count the number of times 1011 occurs in the concatenation of 3 copies of 110, that is, 110110110. We can see it occurs twice:
 - 1 1011 0110
 - 1101 1011 0

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
n = int(input())
t = input()
if n == 1:
	if t == '0':
		print(10 ** 10)
	else:
		print(2 * 10 ** 10)
elif n == 2:
	if t == '00':
		print(0)
	elif t == '01':
		print(10 ** 10 - 1)
	elif t == '10':
		print(10 ** 10)
	else:
		print(10 ** 10)
else:
	repeat_num = (n + 6) // 3
	ref = '110' * repeat_num
	num_in_ref = 0
	flag_over = 0
	if ref[:n] == t:
		num_in_ref += 1
		if n % 3 == 0:
			flag_over = 1
	elif ref[1:n + 1] == t:
		num_in_ref += 1
	elif ref[2:n + 2] == t:
		num_in_ref += 1
		if n % 3 == 2:
			flag_over = -1
	print(num_in_ref * (10 ** 10 - repeat_num + 2) + flag_over)


n = int(input())
t = input()
if t == '1':
	print(10 ** 10 * 2)
elif t == '11':
	print(10 ** 10)
elif '00' in t or '111' in t or '010' in t:
	print(0)
else:
	a = t.count('0')
	if t[-1] == '1':
		print(10 ** 10 - a)
	else:
		print(10 ** 10 - a + 1)


import sys
sys.setrecursionlimit(10 ** 6)

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LC():
	return list(input())

def IC():
	return [int(c) for c in input()]

def MI():
	return map(int, input().split())

def solve():
	N = II()
	T = input()
	if N == 1:
		if T == '0':
			print(10000000000)
			return
		elif T == '1':
			print(20000000000)
			return
	elif N == 2:
		if T == '11' or T == '10':
			print(10000000000)
			return
		elif T == '01':
			print(9999999999)
			return
		else:
			print(0)
			return
	else:
		First = T[:3]
		if First != '110' and First != '101' and (First != '011'):
			print(0)
			return
		for i in range(3, N - 2, 3):
			if First != T[i:i + 3]:
				print(0)
				return
		if N % 3 == 1:
			if First[0] != T[-1]:
				print(0)
				return
		elif N % 3 == 2:
			if First[0:2] != T[-2:]:
				print(0)
				return
		from math import ceil, floor
		if First == '110':
			print(10000000000 - floor((N - 1) / 3))
			return
		elif First == '101' or First == '011':
			print(9999999999 - floor((N - 2) / 3))
			return
	return
solve()


import math
n = int(input())
t = str(input())
len_t = len(t)
len_s = math.ceil(len_t / 3)
if t == '1':
	print(10 ** 10 * 2)
	return
s = ''
for i in range(len_s):
	s += '110'
if t not in s:
	len_s += 1
	s += '110'
if t in s:
	s.find('110')
	print(10 ** 10 - len_s + 1)
else:
	print(0)


N = int(input())
T = list(map(int, list(input())))
if N == 1:
	if T == [1]:
		print(2 * 10 ** 10)
	else:
		print(10 ** 10)
	return
elif N == 2:
	if T == [1, 0] or T == [1, 1]:
		print(10 ** 10)
	elif T == [0, 1]:
		print(10 ** 10 - 1)
	else:
		print(0)
	return
for i in range(N):
	if i == 0:
		if T[i] == 0:
			if T[i + 1] == 0:
				print(0)
				return
			else:
				T[i] = 3
		elif T[i + 1] == 0:
			T[i] = 2
		else:
			T[i] = 1
	elif T[i] == 0:
		if T[i - 1] == 3:
			print(0)
			return
		elif T[i - 1] == 2:
			T[i] = 3
		else:
			print(0)
			return
	elif T[i - 1] == 3:
		T[i] = 1
	elif T[i - 1] == 2:
		print(0)
		return
	else:
		T[i] = 2
A = N - T.index(1) - list(reversed(T)).index(3)
A = A // 3
if T[0] == 1 and T[-1] == 3:
	print(10 ** 10 - A + 1)
elif T[0] == 1 or T[-1] == 3:
	print(10 ** 10 - A)
else:
	print(10 ** 10 - A - 1)


def main():
	num = 10 ** 10
	startnum = 0
	iio = '110'
	N = int(input())
	T = input()
	if T == '1':
		return print(num * 2)
	if T == '0':
		return print(num)
	if T == '11':
		return print(num)
	if T[0] == '1' and T[1] == '1' and (T[2] == '0'):
		startnum = 0
	if T[0] == '1' and T[1] == '0':
		startnum = 1
	if T[0] == '0':
		startnum = 2
	for i in range(N):
		if T[i] != iio[(i + startnum) % 3]:
			return print(0)
	if (N - (3 - startnum)) % 3 == 0:
		return print(num - (N - (3 - startnum)) // 3)
	else:
		return print(num - (N - (3 - startnum)) // 3 - 1)

def __starting_point():
	main()
__starting_point()


n = int(input())
t = input()
s = '110'
if t == '0':
	print(10 ** 10)
	return
elif t == '1':
	print(2 * 10 ** 10)
	return
res = 0
for i in range(3):
	a = (n + i + 2) // 3
	add = 10 ** 10 - a + 1
	ok = True
	for j in range(n):
		if t[j] != s[(i + j) % 3]:
			ok = False
	if ok:
		res += add
print(res)


N = int(input())
T = input()
S = '110' * N
ans = 0
for i in range(3):
	if S[i:i + N] == T:
		ans += 10 ** 10 + -(i + N) // 3 + 1
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def I():
	return int(input())

def LI():
	return list(map(int, input().split()))

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def S():
	return input()

def LS():
	return input().split()
INF = float('inf')
n = I()
t = S()
if n == 1:
	if t == '0':
		print(10 ** 10)
	else:
		print(2 * 10 ** 10)
elif '00' in t or '010' in t or '111' in t:
	print(0)
else:
	start = t[:2]
	if start == '11':
		if n % 3 == 0:
			print(10 ** 10 - n // 3 + 1)
		else:
			print(10 ** 10 - n // 3)
	elif start == '10':
		print(10 ** 10 - n // 3)
	elif n % 3 == 2:
		print(10 ** 10 - n // 3 - 1)
	else:
		print(10 ** 10 - n // 3)


n = int(input())
T = input()
b = 10 ** 10
D = {'0': b, '1': b * 2, '11': b, '10': b, '01': b - 1, '00': 0}
if n < 3:
	print(D[T])
	return
P = ['110', '101', '011']
(h, t) = (-1, -1)
for i in range(3):
	if T[:3] == P[i]:
		h = 3 - i
	if T[-3:] == P[i]:
		t = i
a = 0
if t != -1 and h != -1 and ((n - h - t) % 3 == 0):
	for i in range((n - h - t) // 3):
		if T[h + 3 * i:h + 3 * -~i] != P[0]:
			break
	else:
		a = 10 ** 10 + 1 - (1 if t else 0) - (1 if h else 0) - (n - h - t) // 3
print(a)


n = int(input())
t = input()
ans = 10 ** 10
if t == '0':
	print(ans)
	return
if t == '1':
	print(ans * 2)
	return
if t == '11':
	print(ans)
	return
if t == '10':
	print(ans)
	return
if t == '01':
	print(ans - 1)
	return
if t == '00':
	print(0)
	return
l = 0
r = n
if t[:3] == '110':
	l = 3
elif t[:3] == '101':
	l = 2
elif t[:3] == '011':
	l = 1
else:
	print(0)
	return
if t[n - 3:] == '110':
	r = n
elif t[n - 3:] == '101':
	r = n - 1
elif t[n - 3:] == '011':
	r = n - 2
else:
	print(0)
	return
L = t[:l]
M = t[l:r]
R = t[r:]
if len(M) % 3:
	print(0)
	return
for i in range(len(M) // 3):
	if M[i * 3:i * 3 + 3] != '110':
		print(0)
		return
S = '110110'
LR = L + R
ans -= 2 + len(M) // 3
for l in range(6):
	if S[l:l + len(LR)] == LR:
		ans += 1
print(ans)


n = int(input())
t = input()
ans = 0
s = '110' * 10 ** 6
if s[0:n] == t:
	ans += 10 ** 10 - (n - 1) // 3
if s[1:n + 1] == t:
	ans += 10 ** 10 - n // 3
if s[2:n + 2] == t:
	ans += 10 ** 10 - (n + 1) // 3
print(ans)


n = int(input())
t = input()
if t == '1':
	print(20000000000)
elif n % 3 == 0:
	if t == '110' * (n // 3):
		print(10000000000 - n // 3 + 1)
	elif t == '101' * (n // 3) or t == '011' * (n // 3):
		print(10000000000 - n // 3)
	else:
		print(0)
elif n % 3 == 1:
	if t + '10' == '110' * (n // 3 + 1) or '1' + t + '0' == '110' * (n // 3 + 1) or '11' + t == '110' * (n // 3 + 1):
		print(10000000000 - n // 3)
	else:
		print(0)
elif t + '0' == '110' * (n // 3 + 1) or '1' + t == '110' * (n // 3 + 1):
	print(10000000000 - n // 3)
elif '11' + t + '10' == '110' * (n // 3 + 2):
	print(10000000000 - n // 3 - 1)
else:
	print(0)


N = int(input())
T = input()
if T == '1':
	print(2 * 10 ** 10)
elif T == '11':
	print(10 ** 10)
else:
	s = '110'
	for i in range(N // 3 + 2):
		if T in s:
			print(10 ** 10 - i)
			return
		else:
			s += '110'
	print(0)


def do():
	n = int(input())
	s = input()
	if s == '1':
		print(2 * 10 ** 10)
		return
	if s == '0':
		print(1 * 10 ** 10)
		return
	if s == '10':
		print(1 * 10 ** 10)
		return

	def do(offset):
		can = True
		x = 0
		if offset == 1 or offset == 2:
			x += 1
		for i in range(n):
			offset %= 3
			if offset == 0 or offset == 1:
				if s[i] == '1':
					offset += 1
					continue
				else:
					can = False
			if offset == 2:
				if s[i] == '0':
					offset += 1
					if i > 1 and s[i - 2] == s[i - 1] == '1':
						x += 1
					continue
				else:
					can = False
		if offset == 1 or offset == 2:
			x += 1
		return (can, x)
	for i in range(3):
		(can, x) = do(i)
		if can:
			print(10 ** 10 - x + 1)
			return
	print(0)
do()


N = int(input())
T = input()
ans = 10 ** 10
if T == '1':
	print(ans * 2)
elif T == '0' or T == '11' or T == '110':
	print(ans)
else:
	if T.startswith('10'):
		T = T[2:]
		ans -= 1
	elif T.startswith('0'):
		T = T[1:]
		ans -= 1
	if T.endswith('11'):
		T = T[:len(T) - 2]
		ans -= 1
	elif T.endswith('1'):
		T = T[:len(T) - 1]
		ans -= 1
	if len(T) % 3 == 0:
		for i in range(0, len(T), 3):
			if T[i:i + 3] == '110':
				ans -= 1
			else:
				print(0)
				return
		print(ans + 1)
	else:
		print(0)


n = int(input())
t = input()
s = '110' * 10 ** 5
c = 0
for i in range(3):
	if s[i:i + n] == t:
		c += 10 ** 10 - (n + i - 1) // 3
print(c)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for k in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)
N = INT()
T = input()
K = 10 ** 10
mod = 3
S = '110'
if T == '1':
	print(K * 2)
	return
if T == '11' or T == '10' or T == '0':
	print(K)
	return

def check(m):
	for i in range(N):
		if T[i] != S[(i + m) % mod]:
			return False
	return True
for m in range(mod):
	if check(m):
		N -= 3 - m
		ans = K - ceil(N, 3)
		print(ans)
		break
else:
	print(0)


N = int(input())
T = input()
S = '110' * 10 ** 5
ans = 0
for n in range(3):
	if S[n:n + N] == T:
		ans += 10 ** 10 - (N + n - 1) // 3
print(ans)


N = int(input())
S = input()
from collections import Counter
n = Counter(S)['0']
if S in '110' * (n * 3 + 3):
	if S == '1':
		print(2 * 10 ** 10)
	else:
		ans = 10 ** 10 - n
		if S[-1] == '0':
			ans += 1
		print(ans)
else:
	print(0)


N = int(input())
T = str(input())
mozi = '110' * (N // 3 + 2)
a = mozi.find(T)
if a == -1:
	print(0)
elif T == '1':
	print(10 ** 10 * 2)
else:
	print(10 ** 10 - int((a + N - 1) / 3))


N = int(input())
T = input()
S = '110' * (N + 2)
if T == '1':
	print(10 ** 10 * 2)
elif T == '00':
	print(0)
elif N == 2:
	print(10 ** 10 if T != '01' else 10 ** 10 - 1)
elif T in S:
	if S.startswith(T):
		print(10 ** 10 - (N + 2) // 3 + 1)
	elif S[1:].startswith(T):
		print(10 ** 10 - (N + 3) // 3 + 1)
	else:
		print(10 ** 10 - (N + 4) // 3 + 1)
else:
	print(0)


def main():
	N = int(input())
	T = input()
	if T == '1':
		print(10 ** 10 * 2)
		return
	elif T == '0' or T == '11':
		print(10 ** 10)
		return
	elif '0' not in T:
		print(0)
		return
	T = '1' * (2 - T.index('0')) + T
	for i in range(len(T)):
		if T[i] != ('0' if i % 3 == 2 else '1'):
			print(0)
			return
	ans = 10 ** 10 - (len(T) - 1) // 3
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(700000)

def s_in():
	return input()

def n_in():
	return int(input())

def l_in():
	return list(map(int, input().split()))
n = n_in()
s = s_in()
N = 3 * 10 ** 10
t = '110' * 2 * n
res = 0
if s == '0':
	print(10 ** 10)
	return
if s == '1':
	print(2 * 10 ** 10)
	return
if s == '10':
	print(10 ** 10)
	return
if s == '11':
	print(10 ** 10)
	return
if s == '00':
	print(0)
	return
if s == '01':
	print(10 ** 10 - 1)
	return
if s == t[:n]:
	res += (N - n) // 3 + 1
if s == t[1:n + 1]:
	res += (N - n - 1) // 3 + 1
if s == t[2:n + 2]:
	res += (N - n - 2) // 3 + 1
print(res)


def main():
	ans = 10 ** 10 + 1
	N = int(input())
	T = input()
	if T == '1':
		print(2 * 10 ** 10)
		return
	if T and T[0] == '0':
		T = T[1:]
		ans -= 1
	elif 2 <= len(T) and T[0:2] == '10':
		T = T[2:]
		ans -= 1
	if 2 <= len(T) and T[-2:] == '11':
		T = T[:-2]
		ans -= 1
	elif T and T[-1] == '1':
		T = T[:-1]
		ans -= 1
	for i in range(0, len(T), 3):
		if not T[i:i + 3] == '110':
			print(0)
			return
	print(ans - len(T) // 3)
main()


import sys
input = sys.stdin.readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')
for _ in range(1):
	n = ri()
	t = rs()
	copies = 10000000000.0
	ans = 0
	s = '110' * n
	for i in range(3):
		if t != s[i:i + n]:
			continue
		ans += copies - (i + n - 1) // 3
	print(int(ans))


N = int(input())
T = input()
S = T.replace('110', '')
M = (len(T) - len(S)) // 3
INF = 10 ** 10
if N == 1:
	if T == '1':
		print(2 * INF)
	else:
		print(INF)
	return
if N == 2:
	if T == '11':
		print(INF)
	elif T == '00':
		print(0)
	elif T == '10':
		print(INF)
	else:
		print(INF - 1)
	return
suffix = ['', '0', '10', '110']
prefix = ['110', '11', '1', '']
for x in suffix:
	for y in prefix:
		if T == x + '110' * M + y:
			if x == '' and y == '':
				print(INF - M + 1)
			elif x != '' and y == '':
				print(INF - M)
			elif x == '' and y != '':
				print(INF - M)
			else:
				print(INF - M - 1)
			return
print(0)


N = int(input())
T = input()
if N > 2:
	for i in range(N - 2):
		if int(T[i]) + int(T[i + 1]) + int(T[i + 2]) != 2:
			print(0)
			return
elif T == '00':
	print(0)
	return
if T == '1':
	ans = 2 * 10 ** 10
elif T == '11':
	ans = 10 ** 10
else:
	cnt = T.count('0')
	if T[-1] == '0':
		ans = 10 ** 10 - (cnt - 1)
	else:
		ans = 10 ** 10 - cnt
print(ans)


n = int(input())
t = input()
s = '110' * 100000
sz = 10 ** 10 * 3
st = -1
ed = -1
for i in range(3):
	if s[i:i + len(t)] == t:
		st = i
		ed = i + len(t) - 1
		break
if t == '1':
	print(2 * 10 ** 10)
elif t == '0':
	print(10 ** 10)
elif st == -1:
	print(0)
else:
	a = st + 1
	d = 3
	l = 1
	r = 10 ** 11
	m = -1
	ans = 0
	while l <= r:
		m = (l + r) // 2
		st = a + (m - 1) * d
		if st + len(t) - 1 > sz:
			r = m - 1
		else:
			ans = m
			l = m + 1
	print(ans)


N = int(input())
T = input()
NUM = 10 ** 10
S = '110' * 2 * 10 ** 5
if '111' in T or '00' in T or '010' in T:
	print(0)
elif T == '1':
	print(NUM * 2)
elif T == '11':
	print(NUM)
else:
	zero_cnt = T.count('0')
	if T[-1] == '0':
		print(NUM - zero_cnt + 1)
	else:
		print(NUM - zero_cnt)


n = int(input())
t = input()
t = str(t)
t = list(t)
t.append('#')
if t[0] == '0':
	for i in range(0, n, 3):
		if t[i] != '0':
			if t[i] == '#':
				break
			else:
				print(0)
				return
		if t[i + 1] != '1':
			if t[i + 1] == '#':
				break
			else:
				print(0)
				return
		if t[i + 2] != '1':
			if t[i + 2] == '#':
				break
			else:
				print(0)
				return
if t[0] == '1' and t[1] == '1':
	for i in range(0, n, 3):
		if t[i] != '1':
			if t[i] == '#':
				break
			else:
				print(0)
				return
		elif t[i + 1] != '1':
			if t[i + 1] == '#':
				break
			else:
				print(0)
				return
		if t[i + 2] != '0':
			if t[i + 2] == '#':
				break
			else:
				print(0)
				return
if t[0] == '1' and t[1] == '0':
	for i in range(0, n, 3):
		if t[i] != '1':
			if t[i] == '#':
				break
			else:
				print(0)
				return
		if t[i + 1] != '0':
			if t[i + 1] == '#':
				break
			else:
				print(0)
				return
		if t[i + 2] != '1':
			if t[i + 2] == '#':
				break
			else:
				print(0)
				return
if n == 1:
	if t[0] == '1':
		print(2 * 10 ** 10)
		return
	else:
		print(10 ** 10)
		return
if n == 2:
	if t[0] == '0' and t[1] == '1':
		print(10 ** 10 - 1)
		return
	else:
		print(10 ** 10)
		return
if n % 3 == 0:
	if t[n - 1] == '0':
		p = n // 3
		print(10 ** 10 - p + 1)
	else:
		p = n // 3
		print(10 ** 10 - p)
elif n % 3 == 2:
	if t[0] == '0' and t[n - 1] == '1':
		p = (n - 2) // 3 + 2
		print(10 ** 10 - p + 1)
	else:
		p = n // 3
		print(10 ** 10 - p)
else:
	p = n // 3
	print(10 ** 10 - p)


N = int(input())
T = input()
l = 10 ** 10
s = '110' * (10 ** 5 + 1)
ans = 0
if T == '1':
	ans = l * 2
else:
	for i in range(3):
		if s[i:N + i] == T:
			ans = l - (i + N - 1) // 3
			break
print(ans)


def main():
	n = int(input())
	t = list(input())
	if n < 3:
		if n == 1 and t[0] == '0':
			print(10 ** 10)
			return
		elif n == 1 and t[0] == '1':
			print(2 * 10 ** 10)
			return
		elif n == 2 and t[0] == '1':
			print(10 ** 10)
			return
	count = 0
	left = 0
	right = n
	if t[0] == '0':
		left += 1
		count += 1
	elif t[0] == '1' and t[1] == '0':
		left += 2
		count += 1
	if t[-2] == '1' and t[-1] == '1':
		right -= 2
		count += 1
	elif t[-2] == '0' and t[-1] == '1':
		right -= 1
		count += 1
	diff = right - left
	if diff % 3 != 0:
		print(0)
		return
	for i in range(diff // 3):
		j = 3 * i + left
		if t[j] == '1' and t[j + 1] == '1' and (t[j + 2] == '0'):
			count += 1
		else:
			print(0)
			return
	print(10 ** 10 - count + 1)

def __starting_point():
	main()
__starting_point()


N = int(input())
T = input()
max_num = len(T) // 3 + 2
if max_num >= 10 ** 10:
	max_num = 10 ** 10
check = '110' * max_num
if T not in check:
	print(0)
	return
elif N == 1 and T[0] == '1':
	print(2 * 10 ** 10)
	return
else:
	cnt = 0
	for i in range(len(T)):
		if T[i] == '0':
			cnt += 1
	if T[-1] != '0':
		cnt += 1
ans = 10 ** 10 - cnt + 1
print(ans)


N = int(input())
S = input()
if N == 1:
	if S == '0':
		print(10 ** 10)
	else:
		print(2 * 10 ** 10)
elif S[:2] == '11':
	for i in range(N):
		if i % 3 == 2 and S[i] == '1':
			print(0)
			break
		if i % 3 != 2 and S[i] == '0':
			print(0)
			break
	else:
		print((3 * 10 ** 10 - N) // 3 + 1)
elif S[:2] == '10':
	for i in range(N):
		if i % 3 == 1 and S[i] == '1':
			print(0)
			break
		if i % 3 != 1 and S[i] == '0':
			print(0)
			break
	else:
		print((3 * 10 ** 10 - N - 1) // 3 + 1)
elif S[:2] == '01':
	for i in range(N):
		if i % 3 == 0 and S[i] == '1':
			print(0)
			break
		if i % 3 != 0 and S[i] == '0':
			print(0)
			break
	else:
		print((3 * 10 ** 10 - N - 2) // 3 + 1)
else:
	print(0)


N = int(input())
T = str(input())
mozi = '110' * (N // 3 + 2)
count = 0
for i in range(3):
	if mozi[i:i + len(T)] == T:
		count += 1
if count == 0:
	result = 0
elif T == '1':
	result = 10 ** 10
	result *= 2
elif T == '11':
	result = 10 ** 10
else:
	K = 0
	for t in T:
		if t == '0':
			K += 1
	if T[-1] == '0':
		result = 10 ** 10 - K + 1
	else:
		result = 10 ** 10 - K
print(result)


def inputlist():
	return [int(j) for j in input().split()]
N = int(input())
T = input()
if N == 1:
	if T == '1':
		print(2 * 10 ** 10)
	else:
		print(10 ** 10)
	return
if N == 2:
	if T == '11':
		print(10 ** 10)
		return
	if T == '10':
		print(10 ** 10)
		return
	if T == '01':
		print(10 ** 10 - 1)
		return
	print(0)
	return
from collections import deque
que = deque()
for i in range(N):
	if (i + 1) % 3 == 0:
		que.append('0')
	else:
		que.append('1')
count = 0
ans = -1
while count < 3:
	flag = 0
	if count == 0:
		li = list(que)
		t = ''.join(li)
		if T == t:
			flag = 1
		count += 1
	else:
		que.popleft()
		if (N + count) % 3 != 0:
			que.append('1')
		else:
			que.append('0')
		t = ''.join(list(que))
		if T == t:
			flag = 1
		count += 1
	if flag == 1:
		ans = len(que) + count - 1
		break
if ans == -1:
	print(0)
	return
n = (3 * 10 ** 10 - ans + 3) // 3
print(n)


import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import accumulate
from itertools import product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
INF = float('inf')
num_list = []
str_list = []

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input() for _ in range(N)]

def s_row_list(N):
	return [s_list() for _ in range(N)]

def s_row_str(N):
	return [list(s_input()) for _ in range(N)]

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	n = i_input()
	t = s_input()
	S = '110'
	ok = False
	for i in range(3):
		for j in range(len(t)):
			if t[j] != S[(j + i) % 3]:
				break
		else:
			ok = True
	if not ok:
		print(0)
		return
	elif t == '1':
		print(2 * 10 ** 10)
	elif t == '11':
		print(10 ** 10)
	else:
		c = t.count('0')
		if t[-1] == '0':
			print(10 ** 10 - c + 1)
		else:
			print(10 ** 10 - c)

def __starting_point():
	main()
__starting_point()


N = int(input())
T = input()
if T == '1':
	print(10 ** 10 * 2)
	return
elif T == '0' or T == '10' or T == '11':
	print(10 ** 10)
	return
elif T == '01':
	print(10 ** 10 - 1)
	return
elif T == '00':
	print(0)
	return
left = T[:3]
if left == '110':
	l = 0
else:
	l = 1
right = T[-3:]
if right == '110':
	r = 0
else:
	r = 1
f = '110'
cnt = 0
i = 0
while True:
	if i + 3 > N:
		break
	s = T[i:i + 3]
	if s == f:
		cnt += 1
		i += 3
	elif int(s[0]) + int(s[1]) + int(s[2]) != 2:
		print(0)
		return
	else:
		i += 1
ans = 10 ** 10 - (cnt - 1) - l - r
print(ans)


from math import ceil
N = int(input())
T = input()
if T == '1':
	print(20000000000)
else:
	s = '110' * ceil(2 * N / 3)
	if T not in s:
		print(0)
	elif T[-1] == '0':
		print(10000000000 - (N - 1) // 3)
	else:
		print(10000000000 - T.count('0'))


def solve():
	N = int(input())
	T = input()
	if N == 1:
		return 20000000000 if T == '1' else 10000000000
	T = T.replace('110', 'T')
	if T.startswith('10'):
		T = 'T' + T[2:]
	elif T.startswith('0'):
		T = 'T' + T[1:]
	if T.endswith('11'):
		T = T[:-2] + 'T'
	elif T.endswith('1'):
		T = T[:-1] + 'T'
	if all((t == 'T' for t in T)):
		return 10000000000 - (len(T) - 1)
	else:
		return 0
print(solve())


import sys
input = sys.stdin.readline
N = int(input())
T = input()[:-1]
S = ['110'] * N
S = ''.join(S)
ans = 0
if S[:N] == T:
	ans += (3 * 10 ** 10 - N) // 3 + 1
if S[1:1 + N] == T:
	ans += (3 * 10 ** 10 - 1 - N) // 3 + 1
if S[2:2 + N] == T:
	ans += (3 * 10 ** 10 - 2 - N) // 3 + 1
print(ans)


n = int(input())
s = input()
if n == 1:
	if s == '1':
		print(10 ** 10 * 2)
	else:
		print(10 ** 10)
elif n == 2:
	if s == '11':
		print(10 ** 10)
	elif s == '10':
		print(10 ** 10)
	elif s == '01':
		print(10 ** 10 - 1)
	else:
		print(0)
elif n == 3:
	if s == '110':
		print(10 ** 10)
	elif s == '101':
		print(10 ** 10 - 1)
	elif s == '011':
		print(10 ** 10 - 1)
	else:
		print(0)
elif n == 4:
	if s in ('1101', '1011', '0110'):
		print(10 ** 10 - 1)
	else:
		print(0)
else:
	b = s.split('110')
	try:
		a = b.pop(0)
		c = b.pop()
	except:
		print(0)
		return
	if not a in ('', '0', '10'):
		print(0)
		return
	if not c in ('', '1', '11'):
		print(0)
		return
	if ''.join(b):
		print(0)
		return
	cnt = len(b) + 1
	if a:
		cnt += 1
	if c:
		cnt += 1
	print(10 ** 10 + 1 - cnt)


import sys
n = int(input())
t = input()
if t == '0':
	print(10 ** 10)
elif t == '1':
	print(2 * 10 ** 10)
else:
	s = 0
	e = 0
	if t[:2] == '11':
		s = 0
	elif t[:2] == '10':
		s = 1
	elif t[:2] == '01':
		s = 2
	else:
		print(0)
		return
	check = '110'
	e = s + n - 1
	for i in range(2, n):
		if t[i] != check[(i + s) % 3]:
			print(0)
			return
	print((3 * 10 ** 10 - 1 - e) // 3 + 1)


N = int(input())
T = input()
S = '110' * (int(N / 3) + 3)
a = S.find(T)
if a == -1:
	print(0)
elif T == '1':
	print(10 ** 10 * 2)
else:
	print(10 ** 10 - int((a + N - 1) / 3))


n = int(input())
t = input()
x = '110' * ((n + 2) // 3)
y = x + '110'
if t == '1':
	ans = 10 ** 10 * 2
elif t in x:
	ans = 10 ** 10 - (n + 2) // 3 + 1
elif t in y:
	ans = 10 ** 10 - (n + 2) // 3
else:
	ans = 0
print(ans)


import sys
n = int(input())
s = input()
M = 10000000000
if s == '1':
	print(2 * M)
	return
elif s == '0':
	print(M)
	return
else:
	for i in range(n - 1):
		if s[i] == '0' and s[i + 1] == '0':
			print(0)
			return
	for i in range(n - 2):
		if s[i] == '1' and s[i + 1] == '1' and (s[i + 2] == '1'):
			print(0)
			return
		elif s[i] == '0' and s[i + 1] == '1' and (s[i + 2] == '0'):
			print(0)
			return
if s[-1] == '0':
	m = s.count('0')
	print(M - (m - 1))
else:
	m = s.count('0') + 1
	print(M - (m - 1))


import bisect, collections, copy, heapq, itertools, math, numpy, string, sys

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())
N = I()
T = S()
if T == '1':
	print(10 ** 10 * 2)
	return
ans = 0
X = -N // 3 * -1
ind_X = ('110' * X).find(T)
ind_X1 = ('110' * (X + 1)).find(T)
if not ind_X == -1:
	ans = 10 ** 10 - (X - 1)
elif not ind_X1 == -1:
	ans = 10 ** 10 - (X - 1) - 1
print(ans)


n = int(input())
s = '110'
t = input()
sn = s * ((n + 2) // 3 + 1)
ret = 0
for i in range(3):
	if sn[i:i + n] == t:
		ret += pow(10, 10) - (i + n - 1) // 3
print(ret)


def main():
	n = int(input())
	t = input()
	if t == '1':
		print(2 * 10 ** 10)
		return
	splitted_t = t.split('0')
	if len(splitted_t[0]) > 2 or len(splitted_t[-1]) > 2:
		print(0)
		return
	for sp_ti in splitted_t[1:-1]:
		if len(sp_ti) != 2:
			print(0)
			return
	if splitted_t[-1] == '':
		splitted_t = splitted_t[:-1]
	print(10 ** 10 - len(splitted_t) + 1)

def __starting_point():
	main()
__starting_point()


def main():
	n = int(input())
	t = input()
	v = 10 ** 10
	is_included = False
	first_threes = ['110', '101', '011']
	for first_three in first_threes:
		if t == first_three * (n // 3) + first_three[:n % 3]:
			is_included = True
			break
	if not is_included:
		print(0)
	elif t == '1':
		print(2 * v)
	elif t == '11':
		print(v)
	else:
		num_0 = t.count('0')
		if t[-1] == '0':
			print(v - num_0 + 1)
		else:
			print(v - num_0)

def __starting_point():
	main()
__starting_point()


input()
s = input()
if s == '1':
	print(2 * 10 ** 10)
	return
if s[:2] == '10':
	s = '1' + s
if s[0] == '0':
	s = '11' + s
if s[-2:] == '11':
	s = s + '0'
if s[-2:] == '01':
	s = s + '10'
if s != '110' * (len(s) // 3):
	print(0)
	return
print(10 ** 10 - len(s) // 3 + 1)


import io
import sys
import math
import collections
import decimal
import itertools
sys.setrecursionlimit(1000000)

def is_T_ok(T):
	if T[0] == 0:
		k = 0
	elif T[1] == 0:
		k = 1
	elif T[2] == 0:
		k = 2
	else:
		return False
	for i in range(len(T)):
		if i % 3 == k:
			if T[i] != 0:
				return False
		elif T[i] != 1:
			return False
	return True

def solve(N, T):
	if T == [0]:
		return 10 ** 10
	elif T == [1]:
		return 10 ** 10 * 2
	elif T == [1, 1]:
		return 10 ** 10
	if not is_T_ok(T):
		return 0
	count0 = T.count(0)
	if T[-1] == 0:
		return 10 ** 10 - count0 + 1
	else:
		return 10 ** 10 - count0

def main():
	N = int(input())
	T = list(map(int, input()))
	a = solve(N, T)
	print(a)

def __starting_point():
	main()
__starting_point()


N = int(input())
T = input()
l = 10 ** 10
bad_cases = ['00', '010', '111']
for i in bad_cases:
	if i in T:
		print(0)
		return
if '0' in T:
	zero_cnt = T.count('0')
	if T[N - 1] == '0':
		print(l - zero_cnt + 1)
	else:
		print(l - zero_cnt)
elif T == '1':
	print(l * 2)
else:
	print(l)


N = int(input())
T = str(input())
S = str()
cnt = 0
p = 0
q = 0
for i in range(N):
	S = S + '110'
for i in range(3):
	if S[i:N + i] == T:
		p = i
		q = i + N - 1
		cnt = cnt + 1
		break
z = q // 3 + 1
if cnt == 0:
	print(0)
elif T == '1':
	print(2 * 10 ** 10)
else:
	print(10 ** 10 - (z - 1))


n = int(input())
T = input()
S = '110' * 10 ** 5
ans = 0
l = 10 ** 10
for i in range(3):
	if S[i:i + len(T)] == T:
		ans += l - (n + i - 1) // 3
print(ans)


N = int(input())
T = input()
if N == 1:
	if T == '0':
		print(10 ** 10)
	else:
		print(10 ** 10 * 2)
	return
if N == 2:
	if T == '00':
		print(0)
	if T == '01':
		print(10 ** 10 - 1)
	if T == '10':
		print(10 ** 10)
	if T == '11':
		print(10 ** 10)
	return
zi = 0
for i in range(3):
	if T[i] == '0':
		zi = i
		break
else:
	print(0)
	return
for i in range(N):
	if i % 3 == zi:
		if T[i] != '0':
			print(0)
			return
	elif T[i] != '1':
		print(0)
		return
m = (N + (3 - zi + 2) % 3 + 2) // 3
print(10 ** 10 - m + 1)


import logging
import sys
from inspect import currentframe
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
logging.basicConfig(level=logging.DEBUG)

def dbg(*args):
	id2names = {id(v): k for (k, v) in list(currentframe().f_back.f_locals.items())}
	logging.debug(', '.join((id2names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args)))

def solve(n, t):
	s = '110'
	num = 10000000000.0
	if t == '0':
		return num
	elif t == '1':
		return 2 * num
	ans = 0
	for i in range(3):
		num110 = (len(t) + i + 2) // 3
		ok = True
		for j in range(len(t)):
			if t[j] != s[(i + j) % 3]:
				ok = False
		if ok:
			ans += num - num110 + 1
	return ans

def main():
	n = int(input())
	t = input()
	dbg(len(t))
	t = t.strip()
	dbg(len(t))
	print(int(solve(n, t)))

def __starting_point():
	main()
__starting_point()


n = int(input())
t = input()
s = '110'
com = ''
a = -(-(n * 2) // 3)
for i in range(a):
	com += s
count = 0
for i in range(a * 3 - n + 1):
	if com[i:n + i] == t:
		count += 1
if count == 0:
	print(0)
elif len(com) <= 3:
	print(pow(10, 10) * count)
else:
	print(pow(10, 10) - (a - count))


N = int(input())
T = input()
l = len(T)
if l == 1:
	if T == '1':
		print(2 * 10 ** 10)
	elif T == '0':
		print(10 ** 10)
elif l == 2:
	if T == '11':
		print(10 ** 10)
	elif T == '10':
		print(10 ** 10)
	elif T == '01':
		print(10 ** 10 - 1)
	elif T == '00':
		print(0)
elif l >= 3:
	s = '110'
	flag = False
	flag110 = False
	index = 0
	for j in range(3):
		index = j
		f = True
		for i in range(l):
			if s[index] != T[i]:
				f = False
			index = (index + 1) % 3
		if f:
			flag = True
		if j == 0 and f and (l % 3 == 0):
			flag110 = True
	if flag110:
		print(10 ** 10 - l // 3 + 1)
	elif flag and T[0] == '0':
		print(10 ** 10 - (l + 1) // 3)
	elif flag:
		print(10 ** 10 - l // 3)
	else:
		print(0)


n = int(input())
t = input()
if n == 1:
	if t == '0':
		print(10 ** 10)
	elif t == '1':
		print(2 * 10 ** 10)
elif n == 2:
	if t == '11' or t == '10':
		print(10 ** 10)
	elif t == '01':
		print(10 ** 10 - 1)
	else:
		print(0)
elif n == 3:
	if t not in ['110', '101', '011']:
		print(0)
		return
	if t == '110':
		print(10 ** 10)
	else:
		print(10 ** 10 - 1)
else:
	check_num_zero = list(set(t.split('1')))
	check_num_one = list(set(t.split('0')))
	for i in check_num_zero:
		if i not in ['', '0']:
			print(0)
			return
	for i in check_num_one:
		if i not in ['', '1', '11']:
			print(0)
			return
	ans = t.split('110')
	if set(ans) == {''}:
		ans = 10 ** 10 - len(ans) + 2
	elif ans[0] == '' or ans[-1] == '':
		ans = 10 ** 10 - len(ans) + 1
	else:
		ans = 10 ** 10 - len(ans)
	print(ans)


n = int(input())
t = input()
baseS = '110'
lenS = 10 ** 10
if t == '0':
	out = lenS
elif t == '1':
	out = lenS * 2
else:
	out = 0
	for chOffset in range(3):
		iter = (chOffset + n + 2) // 3
		num1 = lenS - iter + 1
		isMatched = True
		for j in range(n):
			if t[j] != baseS[(j + chOffset) % 3]:
				isMatched = False
		if isMatched:
			out += num1
print(out)


import sys
N = int(input())
T = input()
if T == '0':
	print(10 ** 10)
	return
elif T == '1':
	print(2 * 10 ** 10)
	return
elif T == '11' or T == '10':
	print(10 ** 10)
	return
elif T == '01':
	print(10 ** 10 - 1)
	return
if T[0] == '0':
	T = '11' + T
elif T[0] == '1' and T[1] == '0':
	T = '1' + T
for i in range(len(T)):
	if i % 3 == 2 and T[i] != '0':
		print(0)
		return
	elif i % 3 != 2 and T[i] != '1':
		print(0)
		return
T_amnt = len(T)
T_sho = T_amnt // 3
T_amari = T_amnt % 3
if T_amari == 0:
	amari = 1
else:
	amari = 0
print(10 ** 10 - T_sho + amari)


d = 3 * 10 ** 10
n = int(input())
s = input()
a = 0
b = 0
i = 0
j = n - 1
while i < n and s[i] == '1':
	i += 1
	a += 1
while j >= 0 and s[j] == '1':
	b += 1
	j -= 1
if n == 1 and s[0] == '1':
	print(d // 3 * 2)
elif a <= 2 and b <= 2:
	if not (j - i) % 3:
		x = '011' * ((j - i) // 3)
		if x == s[i:j]:
			maxindex = d + 1 - n
			if n == 1:
				if s[0] == '1':
					print(d // 3 * 2)
				else:
					print(d // 3)
			elif a == 0:
				print(maxindex // 3)
			elif a == 1:
				print((maxindex + 1) // 3)
			else:
				print((maxindex + 2) // 3)
		else:
			print(0)
	else:
		print(0)
else:
	print(0)


from sys import stdin, setrecursionlimit
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import accumulate, combinations, combinations_with_replacement, permutations
from math import ceil, sqrt, pi, radians, sin, cos, log
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)
INF = 10 ** 18
N = int(input())
T = input()
if N == 1:
	if T == '0':
		print(10 ** 10)
	else:
		print(10 ** 10 * 2)
	return
if N == 2:
	if T == '00':
		print(0)
	elif T == '01':
		print(10 ** 10 - 1)
	elif T == '10':
		print(10 ** 10)
	else:
		print(10 ** 10)
	return

def f(T):
	U = (N // 3 + 5) * '110'
	for i in range(3):
		flag = True
		for j in range(len(T)):
			if T[j] != U[i + j]:
				flag = False
				break
		if flag:
			(l, r) = ((3 - i) % 3, (i + len(T)) % 3)
			tmp = (N - l - r) // 3
			if l:
				tmp += 1
			if r:
				tmp += 1
			return 10 ** 10 - tmp + 1
	return 0
print(f(T))


from sys import stdin
pin = stdin.readline

def main():
	N = int(pin())
	T = pin().rstrip()
	if N == 1:
		if T[0] == '0':
			print(pow(10, 10))
		else:
			print(2 * pow(10, 10))
	elif N == 2:
		if T[0] == '0':
			if T[1] == '0':
				print(0)
			else:
				print(pow(10, 10) - 1)
		elif T[1] == '0':
			print(pow(10, 10))
		else:
			print(pow(10, 10))
	elif T[0] == '1' and T[1] == '1' and (T[2] == '0'):
		for i in range(N):
			if i % 3 in [0, 1]:
				if T[i] != '1':
					print(0)
					return
			if i % 3 == 2:
				if T[i] != '0':
					print(0)
					return
		t = N % 3
		s = N // 3
		if t == 0:
			print(pow(10, 10) - s + 1)
		else:
			print(pow(10, 10) - s)
	elif T[0] == '1' and T[1] == '0' and (T[2] == '1'):
		for i in range(N):
			if i % 3 in [0, 2]:
				if T[i] != '1':
					print(0)
					return
			if i % 3 == 1:
				if T[i] != '0':
					print(0)
					return
		t = N % 3
		s = N // 3
		if t == 0:
			print(pow(10, 10) - s)
		else:
			print(pow(10, 10) - s)
	elif T[0] == '0' and T[1] == '1' and (T[2] == '1'):
		for i in range(N):
			if i % 3 in [1, 2]:
				if T[i] != '1':
					print(0)
					return
			if i % 3 == 0:
				if T[i] != '0':
					print(0)
					return
		t = N % 3
		s = N // 3
		if t == 2:
			print(pow(10, 10) - s - 1)
		else:
			print(pow(10, 10) - s)
	else:
		print(0)
	return
main()


N = int(input())
T = input()
if T == '1':
	print(2 * 10 ** 10)
	return
c = 1
if T[0] == '0':
	c1 = 0
else:
	c1 = 1
T = T[1:]
for t in T:
	if t == '1':
		if c1 == 2:
			print(0)
			return
		elif c1 == 0:
			c += 1
		c1 += 1
	if t == '0':
		if c1 == 0 or (c > 1 and c1 == 1):
			print(0)
			return
		c1 = 0
print(10 ** 10 - c + 1)


N = int(input())
T = input()
nums = [1, 1, 0]
ans1 = []
ans2 = []
ans3 = []
for n in range(N):
	ans1.append(str(nums[n % 3]))
for n in range(1, N + 1):
	ans2.append(str(nums[n % 3]))
for n in range(2, N + 2):
	ans3.append(str(nums[n % 3]))
s_ans1 = ''.join(ans1)
s_ans2 = ''.join(ans2)
s_ans3 = ''.join(ans3)
if T == '1':
	print(pow(10, 10) * 2)
elif T == '11':
	print(pow(10, 10))
elif T == '0':
	print(pow(10, 10))
elif s_ans1 == T or s_ans2 == T or s_ans3 == T:
	if T[-1] == '0':
		print(pow(10, 10) - T.count('0') + 1)
	else:
		print(pow(10, 10) - T.count('0'))
else:
	print(0)


n = int(input())
s = input()
flag = True
if n == 1:
	if s == '0':
		print(pow(10, 10))
	elif s == '1':
		print(pow(10, 10) * 2)
elif n == 2:
	if s in ['11', '10']:
		print(pow(10, 10))
	elif s == '01':
		print(pow(10, 10) - 1)
	else:
		print(0)
else:
	flag = True
	f = n // 3
	r = n % 3
	for i in range(0, n, 3):
		if i == 0:
			ans = s[0:3]
			if ans not in ['110', '101', '011']:
				flag = False
				break
		elif i < 3 * f:
			tmp = s[i:i + 3]
			if tmp != ans:
				flag = False
				break
		else:
			tmp = s[i:n]
			if tmp != ans[0:n - i]:
				flag = False
				break
	if not flag:
		print(0)
	elif ans == '110':
		if r == 0:
			print(pow(10, 10) - f + 1)
		else:
			print(pow(10, 10) - f)
	elif ans == '101':
		print(pow(10, 10) - f)
	elif ans == '011':
		if r < 2:
			print(pow(10, 10) - f)
		else:
			print(pow(10, 10) - f - 1)


import sys
import os
from copy import copy
import operator
import time
import datetime
import math
from math import floor, ceil, sqrt, log
import statistics
from statistics import mean, median
from decimal import Decimal as D
from fractions import Fraction as F
import functools
import random
from random import randint, shuffle
import bisect
import string
from collections import deque
import collections
import itertools
import heapq
sys.setrecursionlimit(4100000)
product = functools.partial(functools.reduce, operator.mul)
INF = float('inf')

class UnionFind:

	def __init__(self, n):
		self.parents = [-1] * n

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x != y:
			if self.parents[x] > self.parents[y]:
				(x, y) = (y, x)
			self.parents[x] += self.parents[y]
			self.parents[y] = x

	def find(self, x):
		if self.parents[x] < 0:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return list(filter(lambda x: x < 0, self.parents))

	def group_count(self):
		return len(self.roots())

	def max_size(self):
		return -min(self.parents)

	def min_size(self):
		return -max(self.roots())

	def append(self, n):
		self.parents += [-1] * n

class Imos:

	def __init__(self, n):
		self.val = [0] * n

	def add(self, x, y, n=None):
		if n is None:
			n = 1
		self.val[x] += n
		if len(self.val) > y + 1:
			self.val[y + 1] -= n

	def imos(self):
		for i in range(1, len(self.val)):
			self.val[i] += self.val[i - 1]

	def max(self):
		return max(self.val)

	def min(self):
		return min(self.val)

class CS:

	def __init__(self, grid):
		self.cs = grid
		for i0 in range(len(grid)):
			for i1 in range(len(grid[0])):
				if i0 == 0:
					if i1 == 0:
						continue
					self.cs[i0][i1] += self.cs[i0][i1 - 1]
				elif i1 == 0:
					self.cs[i0][i1] += self.cs[i0 - 1][i1]
				else:
					self.cs[i0][i1] += self.cs[i0 - 1][i1] + self.cs[i0][i1 - 1] - self.cs[i0 - 1][i1 - 1]

	def sum(self, start_0, start_1, end_0, end_1):
		if start_0 == 0:
			if start_1 == 0:
				return self.cs[end_0][end_1]
			return self.cs[end_0][end_1] - self.cs[end_0][start_1 - 1]
		if start_1 == 0:
			return self.cs[end_0][end_1] - self.cs[start_0 - 1][end_1]
		start_0 -= 1
		start_1 -= 1
		return self.cs[end_0][end_1] - self.cs[start_0][end_1] - self.cs[end_0][start_1] + self.cs[start_0][start_1]

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

def sinput():
	return sys.stdin.readline()[:-1]

def input():
	inputs = list(map(int, sys.stdin.readline().split()))
	if len(inputs) == 1:
		return inputs[0]
	return inputs

def listban(l):
	return list(map(list, set(map(tuple, l))))

def div(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

def prime(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def div_counter(l, n):
	return prime(l).count(n)

def lcm(x, y):
	return x * y // math.gcd(x, y)

def C(n, r):
	if n < r:
		return 0
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def P(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(n - r)

def H(n, r):
	return C(n + r - 1, r)

def cos(x, y, a):
	return (x ** 2 + y ** 2 - 2 * x * y * math.cos(math.radians(a))) ** 0.5

def DFS(g, s, pos=None):
	if pos is None:
		pos = set()
	pos.add(s)
	for i in g[s]:
		if not i in pos:
			DFS(g, i, pos)
	return pos

def DFS_one(g, s, pos=None):
	if pos is None:
		pos = set()
	pos = copy(pos)
	pos.add(s)
	b = copy(pos)
	m = copy(pos)
	for i in g[s]:
		if not i in pos:
			b = DFS(g, i, pos)
			if len(m) < len(b):
				m = b
	return m

def BFS(g, q, pos=None):
	if pos is None:
		pos = set()
	if type(q) == deque:
		pos.add(q)
		q = deque([q])
	pos.add(q[-1])
	for i in g[q.pop()]:
		if not i in pos:
			q.append(i)
	while q != deque():
		(pos, q) = BFS(g, q, pos)
	return (pos, q)

def SSP(a, li=None):
	if li is None:
		li = []
	if len(a) == 1:
		return [a[0]]
	return list(set(li + SSP(a[1:], li) + list(map(lambda x: x + a[0], SSP(a[1:], li))) + [a[0]]))

def dijkstra(g, s):
	n = len(g)
	dist = [10 ** 100] * n
	hq = [(0, s)]
	dist[s] = 0
	seen = [False] * n
	while hq:
		v = heapq.heappop(hq)[1]
		seen[v] = True
		for (to, cost) in g[v]:
			if seen[to] == False and dist[v] + cost < dist[to]:
				dist[to] = dist[v] + cost
				heapq.heappush(hq, (dist[to], to))
	return dist

def LIS(b):
	l = [b[0]]
	for i in b:
		if i > l[-1]:
			l += [i]
		else:
			l[bisect.bisect_left(l, i)] = i
	return len(l)

def yn(b):
	if b:
		print('Yes')
	else:
		print('No')

def op(s):
	print(s)
	return
n = input()
t = sinput()
if '00' in t:
	print(0)
elif '111' in t:
	print(0)
elif '010' in t:
	print(0)
elif t == '0':
	print(10 ** 10)
elif t == '1':
	print(10 ** 10 * 2)
else:
	if t[-2:] == '11':
		t = t + '0'
	elif t[-2:] == '01':
		t = t + '10'
	if t[:2] == '10':
		t = '1' + t
	elif t[:2] == '01':
		t = '11' + t
	print(10 ** 10 + 1 - len(t) // 3)


n = int(input())
t = input()
if t == '1':
	print(2 * 10 ** 10)
else:
	if '0' in t:
		first_zero = t.index('0')
	else:
		first_zero = n
	if first_zero < 3 and all((c == '1' for c in t[:first_zero])):
		num_of_110 = 0
		curr = t[first_zero + 1:]
		while len(curr) > 3 and curr.startswith('110'):
			num_of_110 += 1
			curr = curr[3:]
		if curr in ['1', '11', '110']:
			num_of_110 += 1
		elif not curr:
			pass
		else:
			print(0)
			import sys
			return
		print(10 ** 10 - num_of_110)
	else:
		print(0)


n = int(input())
t = input()
p = '110' * (n // 3 + 2)
if p[:n] != t and p[1:n + 1] != t and (p[2:n + 2] != t):
	ans = 0
elif t == '1':
	ans = 2 * 10 ** 10
elif t == '11':
	ans = 10 ** 10
else:
	k = 0
	for c in t:
		if c == '0':
			k += 1
	if t[-1] == '0':
		ans = 10 ** 10 - (k - 1)
	else:
		ans = 10 ** 10 - k
print(ans)


N = int(input())
T = input()
V = 10 ** 10
if T == '1':
	print(2 * V)
	return
elif T == '11' or T == '0':
	print(V)
	return
else:
	K = T.count('0')
	data = '110' * (K + 1)
	if data.count(T) == 0:
		print(0)
	elif T[-1] == '0':
		print(10 ** 10 - K + 1)
	else:
		print(10 ** 10 - K)


n = int(input())
t = input()
if t == '1':
	print(10 ** 10 * 2)
elif t == '0':
	print(10 ** 10)
elif t == '11' or t == '10':
	print(10 ** 10)
elif t == '01':
	print(10 ** 10 - 1)
elif t == '110':
	print(10 ** 10)
elif t == '101' or t == '011':
	print(10 ** 10 - 1)
elif '00' in t or '010' in t or '111' in t:
	print(0)
elif t[0:2] == '11' and n % 3 == 0:
	print(10 ** 10 - n // 3 + 1)
elif t[0:2] == '01' and n % 3 == 2:
	print(10 ** 10 - n // 3 - 1)
else:
	print(10 ** 10 - n // 3)


from sys import stdin, setrecursionlimit
import bisect, collections, copy, heapq, itertools, math, string
setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 1000000007

def input():
	return stdin.readline().strip()

def main():
	n = int(input())
	t = input()
	a = 10 ** 10
	ans = 0
	if n == 1:
		if t == '1':
			ans = a * 2
		elif t == '0':
			ans = a
	elif n == 2:
		if t in {'11', '10'}:
			ans = a
		elif t == '01':
			ans = a - 1
	elif n == 3:
		if t == '110':
			ans = a
		elif t in {'101', '011'}:
			ans = a - 1
	else:
		now = 0
		pre = t[:2]
		if pre == '11':
			now = 0
		elif pre == '10':
			now = 1
		elif pre == '01':
			now = 2
		else:
			print(0)
			return
		for char in t:
			flag = False
			if now in {0, 1}:
				if char != '1':
					flag = True
			if now == 2:
				if char != '0':
					flag = True
			now += 1
			if now == 3:
				now = 0
			if flag:
				print(0)
				return
		x = n if pre == '11' else n + 1 if pre == '10' else n + 2
		ans = a - ((x + 3 - 1) // 3 - 1)
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


n = int(input())
t = input()
if n == 1:
	if t == '1':
		print(2 * 10 ** 10)
	else:
		print(10 ** 10)
elif n == 2:
	if t == '11' or t == '10':
		print(10 ** 10)
	elif t == '01':
		print(10 ** 10 - 1)
	else:
		print(0)
else:
	if t[:3] == '110':
		a = 0
	elif t[:3] == '101':
		a = 1
	elif t[:3] == '011':
		a = 2
	else:
		print(0)
		return
	b = a
	for i in t[3:]:
		if i != '110'[b % 3]:
			print(0)
			return
		b += 1
	print(10 ** 10 - (a + n - 1) // 3)


n = int(input())
T = input()
mod = None
for i in range(n):
	if T[i] == '0':
		mod = i % 3
		break
if mod is None:
	if n == 1:
		print(2 * 10 ** 10)
	elif n == 2:
		print(10 ** 10)
	else:
		print(0)
	return
for i in range(n):
	if (T[i] == '0') != (i % 3 == mod):
		print(0)
		return
print(10 ** 10 - (n - mod + 4) // 3 + 1)


def solve():
	N = int(input())
	T = input()
	if T == '1':
		print(10 ** 10 * 2)
		return
	splited = T.split('0')
	if len(splited[0]) > 2 or len(splited[-1]) > 2:
		print('0')
		return
	for i in range(1, len(splited) - 1):
		if len(splited[i]) != 2:
			print('0')
			return
	if len(splited) - 1 > 10 ** 10:
		print('0')
		return
	if T[-1] == '0':
		print(10 ** 10 - (len(splited) - 1) + 1)
	else:
		print(10 ** 10 - (len(splited) - 1))

def __starting_point():
	solve()
__starting_point()


n = int(input())
s = input()
x = -(-n // 3)
if s not in '110' * (x + 1):
	print(0)
elif s == '0' or s == '11' or s == '10':
	print(10 ** 10)
elif s == '1':
	print(10 ** 10 * 2)
elif s == '01':
	print(10 ** 10 - 1)
elif s in x * '110':
	print(10 ** 10 - x + 1)
else:
	print(10 ** 10 - x)


def solve(n, t):
	m = 10 ** 10
	ans = 0
	s = '110' * n
	for i in range(3):
		if s[i:len(t) + i] == t:
			ans += (3 * m - i - n) // 3 + 1
	return ans
n = int(input())
t = input()
print(solve(n, t))


import math
import copy
import bisect
from itertools import accumulate
from collections import Counter, defaultdict, deque

def mp():
	return list(map(int, input().split()))

def lmp():
	return list(map(int, input().split()))

def ceil(U, V):
	return (U + V - 1) // V

def modf1(N, MOD):
	return (N - 1) % MOD + 1
n = int(input())
t = input()
if n == 1:
	if t == '0':
		print(int(10000000000.0))
		return
	else:
		print(int(20000000000.0))
		return
if n == 2:
	if t == '11' or t == '10':
		print(int(10000000000.0))
		return
	elif t == '01':
		print(int(10000000000.0 - 1))
		return
	else:
		print(0)
		return
if t[:3] == '110':
	if n % 3 == 0:
		if t != '110' * (n // 3):
			print(0)
			return
	elif n % 3 == 1:
		if t != '110' * (n // 3) + '1':
			print(0)
			return
	elif n % 3 == 2:
		if t != '110' * (n // 3) + '11':
			print(0)
			return
	print(int(10000000000.0) - ceil(n, 3) + 1)
elif t[:3] == '101':
	if n % 3 == 0:
		if t != '101' * (n // 3):
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3))
	elif n % 3 == 1:
		if t != '101' * (n // 3) + '1':
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3) + 1)
	elif n % 3 == 2:
		if t != '101' * (n // 3) + '10':
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3) + 1)
elif t[:3] == '011':
	if n % 3 == 0:
		if t != '011' * (n // 3):
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3))
	elif n % 3 == 1:
		if t != '011' * (n // 3) + '0':
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3) + 1)
	elif n % 3 == 2:
		if t != '011' * (n // 3) + '01':
			print(0)
			return
		print(int(10000000000.0) - ceil(n, 3))
else:
	print(0)


N = int(input())
T = input()
S = '110' * N
if T == '1':
	print(2 * 10 ** 10)
	return
for i in range(3):
	if S[i:N + i] == T:
		print((3 * 10 ** 10 - N - i) // 3 + 1)
		return
print(0)