#include"bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back
#define all(v) begin(v), end(v)
#define inf (int)(4e18)
#define N (int)(2e5 + 10)

int isPos(int x, int n, int i) {
     if (i > 2) return 0;
     int len = 3 * (1e10);
     return 3 * (x - 1) + i + n - 1 < len;
}

bool check(string &s, string t) {
     int n = s.length();
     for (int i = 0; i < n; i += 3) {
          int got = min(3ll, n - i);
          string tukda = s.substr(i, got);
          string toMatch = t.substr(0, got);
          if (tukda != toMatch) {
               // dbg(tukda, toMatch);
               return false;
          }
     }
     return true;
}

void testCase() {
     int n; cin >> n;
     string s; cin >> s;
     if (s == "1") {cout << (int)2e10; return;}
     int type = 3;
     if (check(s, "110")) type = 0;
     else if (check(s, "101")) type = 1;
     else if (check(s, "011")) type = 2;
     int mi = 0, ma = 1;
     while (isPos(ma, n, type)) ma *= 2;
     while (mi + 1 < ma) {
          int mid = (mi + ma) / 2;
          if (isPos(mid, n, type)) mi = mid;
          else ma = mid;
     }

     cout << mi;
}

/* Work hard .. Calm and proceed */
int32_t main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr), cout.tie(nullptr);
     int t_c = 1;
     // cin >> t_c;
     while (t_c--)
          testCase();
}
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <unordered_map>
#include <cstdio>
#include <climits>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

const ll INF = 10000000000;

int n;
string s;

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> n >> s;
	if (n == 1) {
		if (s == "0")cout << INF << endl;
		else cout << 2 * INF << endl;
		return 0;
	}
	int p = s[0] - '0', cnt = 1;
	for (int i = 1; i < n; i++) {
		if (s[i - 1] == s[i])cnt++;
		else {
			if (p == 0) {
				if (cnt != 1) {
					cout << 0 << endl;
					return 0;
				}
				else cnt = 1, p = 1;
			}
			else {
				if (cnt > 2 || (cnt < 2 && cnt < i)) {
					cout << 0 << endl;
					return 0;
				}
				else cnt = 1, p = 0;
			}
		}
	}
	if (p == 0 && cnt != 1) {
		cout << 0 << endl;
		return 0;
	}
	if (p == 1 && cnt > 2) {
		cout << 0 << endl;
		return 0;
	}
	int d = 0;
	if (s.substr(0, 2) == "10")d = 1;
	if (s.substr(0, 2) == "01")d = 2;
	ll x = 3 * INF - n;
	while (x % 3 != d)x--;
	cout << (x - d) / 3 + 1 << endl;
}