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: interview

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:  # 11
        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(ref[: n + 1], t)
    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))
else:
    if "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))


#https://qiita.com/goto_yuta_/items/1c104e332351ab9389a6
# 入力を整数に変換して受け取る
import sys
sys.setrecursionlimit(10 ** 6)#pypy3はnumpyを使えない，この行を消すこと．
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力の文字列を1文字ずつに分けたものの配列を受け取る
def LC(): return list(input())
# 入力の数字列を1桁ずつに分けたものの配列を受け取る
def IC():return [int(c) for c in input()]
#少ない1行のint変数に入れる様の入力．例:N, A, B = map(int, input().split())
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]):#最初の1文字と末尾の1文字の一致
                print(0)
                return
        elif(N%3 == 2):
            if(First[0:2] != T[-2:]):#最初の2文字と末尾の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
    else:
      if T[i+1]==0:
        T[i]=2
      else:
        T[i]=1
  else:
    if T[i]==0:
      if T[i-1]==3:
        print(0)
        return
      elif T[i-1]==2:
        T[i]=3
      else:
        print(0)
        return
    else:
      if 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')

# 50
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))
    else:
        if 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 # M=[l,r)
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)
else:
  if 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("offset", i, x)
            print((10**10 - x + 1))
            return
    print((0))



do()


# B - Many 110
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())
S = '110'*N
T = input()
ans = 0
for i in range(3):
  if S[i:i+N]==T:
    ans = pow(10,10)-(i+N-1)//3-i//3
    break
if T=='1':
  ans = 2*pow(10,10)
print(ans)

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)

    
    
    


"""
prefix: "0", "10"
sufix:  "1", "11"
"""
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
#print=sys.stdout.write
#sys.setrecursionlimit(100000)
#from heapq import *
#from collections import deque as dq
#from math import ceil,floor,sqrt,gcd,log
#import bisect as bs
#from collections import Counter
#from collections import defaultdict as dc 
#from functools import reduce
#from functools import lru_cache
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=1e10
    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 = "110" * (10 ** 5)
ans = 0
for i in range(3):
  if s[i:i + n] == t:
    ans += 10 ** 10 - (n + i - 1) // 3
print(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

# print(len(s))

st = -1
ed = -1
for i in range(3):
    if s[i:i+len(t)] == t:
        st = i
        ed = i + len(t) - 1
        break

# print("st = ", st)
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
        # print(m, st, st+len(t)-1)
        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')
    # print(zero_cnt)
    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))




#!/usr/bin/env python
# coding: utf-8

# In[1]:


N = int(input())
T = input()


# In[2]:


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)


# In[ ]:






# -*- coding: utf-8 -*-


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)


# -*- coding: utf-8 -*-


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
        elif n == 2 and t[0] == "0" and t[1] == "1":
            print((10 ** 10 - 1))
            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())
S = input()

if N == 1:
    if S == '0':
        print(10**10)
    else:
        print(2 * 10**10)

else:
    if 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)

n = int(input())
t = input()
ans = 0

s = "110" * 10**6


if s[0:n] == t:
    ans += 10**10 - (n-1)//3
    # if n%3 == 0:
    #     ans += 1

if s[1:n+1] == t:
    ans += 10**10 - n//3
    # if n%3 == 0:
    #     ans += 1
    
if s[2:n+2] == t:
    ans += 10**10 - (n+1)//3
    # if n%3 == 0:
    #     ans += 1

print(ans)

#template
def inputlist(): return [int(j) for j in input().split()]
#template
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
# input = sys.stdin.readline 
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"
    #s = "110" * (n // 3 * 2)

    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
    else:
        if 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)
    else:
        if 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 20_000_000_000 if T == "1" else 10_000_000_000
    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 10_000_000_000 - (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())
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:  # 11
        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
    if ref[1 : n + 1] == t:
        num_in_ref = 1
    if ref[2 : n + 2] == t:
        num_in_ref = 1
        if n % 3 == 2:
            flag_over = -1
    print(num_in_ref * (10 ** 10 - n//3) + flag_over)

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()

s = "110" * (10 ** 5)

if t == "1":
    print(2 * 10 ** 10)
    return


for i in range(3):
    if t == s[i : i + n]:
        print(1 + (3 * 10 ** 10 - (i + n)) // 3)
        return

print(0)

# -*- coding: utf-8 -*-


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
        elif n == 2 and t[0] == "0" and t[1] == "1":
            print((10 ** 10 - 1))
            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()


if "111" in t or "00" in t or "010" in t:
    ans = 0
elif t == "1":
    ans = 2 * (10 ** 10)
elif t == "11":
    ans = 10 ** 10
elif t[-1] == "0":
    ans = 10 ** 10 - t.count("0") + 1
elif t[-1] == "1":
    ans = 10 ** 10 - t.count("0")
    
print(ans)


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

    # tがSに含まれているか
    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))
    else:
        if 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))


#!/usr/bin/env python3
# from typing import *

import io
import sys
import math
import collections
import decimal
import itertools

sys.setrecursionlimit(1000000)

# _INPUT = """2
# 01
# """
# sys.stdin = io.StringIO(_INPUT)

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
        else:
            if 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"
#print(S)
for i in range(3):
  #print(i,S[i:N+i],T)
  if S[i:N+i]==T:
    p=i
    q=i+N-1
    cnt=cnt+1
    #print("p",i)
    break
z=q//3+1

#print(z)
#print(cnt)

if cnt==0:
  print(0)
else:
  if T=="1":
    print(2*10**10)
  else:
    print(10**10-(z-1))

import sys
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000)
#from heapq import *
#from collections import deque as dq
#from math import ceil,floor,sqrt,gcd,log
#import bisect as bs
#from collections import Counter
#from collections import defaultdict as dc 
#from functools import reduce
#from functools import lru_cache
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=1e10
    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 = "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))


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
    else:
        if 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 = 1e10
    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 = ''

#print((n*2)//3)
#切り上げ個数
#print(-(-(n*2)//3))

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 
#elif t == "11":
#    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 # log(25, 5) = 5.0
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"
    #print(U)
    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)
    else:
      if T[1]=="0":
        print(pow(10,10))
      else:
        print(pow(10,10))
  else:
    if 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()
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)

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)
    else:
        if 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]
                else:
                    if 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)

# TODO refactor

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)
    else:  
      
      if 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)
else:
    if s in x*'110':
        print(10**10-x+1)
    else:
        print(10**10-x)

N = int(input())
T = input()
S = "110" * 10**6

if T == "0":
    print(10**10)
elif T == "1":
    print(2*10**10)
elif T == "11":
    print(10**10)
else:
    for i in range(3):
        if S[i:N+i] == T:
            print(10**10 - ((N+2) // 3 - 1) - ((i+N+2) // 3 > (N+2) // 3))
            return
    print(0)

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 sys
# input = sys.stdin.readline
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(1e10)))
        return
    else:
        print((int(2e10)))
        return
if n == 2:
    if t == "11"or t == "10":
        print((int(1e10)))
        return
    elif t == "01":
        print((int(1e10-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(1e10)-ceil(n,3)+1))

elif t[:3] == "101":
    if n % 3 == 0:
        if t != "101"*(n//3):
            print((0))
            return
        print((int(1e10) - ceil(n, 3)))
    elif n % 3 == 1:
        if t != "101"*(n//3)+"1":
            print((0))
            return
        print((int(1e10) - ceil(n, 3) + 1))
    elif n % 3 == 2:
        if t != "101"*(n//3)+"10":
            print((0))
            return
        print((int(1e10)-ceil(n,3)+1))

elif t[:3] == "011":
    if n % 3 == 0:
        if t != "011"*(n//3):
            print((0))
            return
        print((int(1e10) - ceil(n, 3)))
    elif n % 3 == 1:
        if t != "011"*(n//3)+"0":
            print((0))
            return
        print((int(1e10) - ceil(n, 3)+1))
    elif n % 3 == 2:
        if t != "011"*(n//3)+"01":
            print((0))
            return
        print((int(1e10)-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)