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

int main() {
    int N;
    string T;
    cin >> N >> T;
    auto solve = [&]() -> long long {
        long long V = 10000000000LL;
        if (T == "0") return V;
        else if (T == "1") return V * 2;

        if (T.size() >= 1 && T.substr(0, 1) == "0") T = T.substr(1), --V;
        else if (T.size() >= 2 && T.substr(0, 2) == "10") T = T.substr(2), --V;
        if (T.size() % 3 == 1) {
            if (T.substr(T.size()-1) != "1") return 0;
            T = T.substr(0, T.size()-1);
            --V;
        }
        else if (T.size() % 3 == 2) {
            if (T.substr(T.size()-2) != "11") return 0;
            T = T.substr(0, T.size()-2);
            --V;
        }
        for (int i = 0; i < T.size(); i += 3) if (T.substr(i, 3) != "110") return 0;
        return V - T.size()/3 + 1;
    };
    cout << solve() << endl;
}
#include<cstdio>

int main(){
    unsigned N;
    scanf("%u\n", &N);
    bool T[N];
    char tmp;
    for (unsigned i = 0; i < N; i++){
        scanf("%c", &tmp);
        T[i] = tmp == '1';
    }
    unsigned long long answer = 0;
    bool flag = true;
    for (unsigned i = 0; i < N; i++){
        if(T[i] ^ (i%3 != 2)){
            flag = false;
            break;
        }
    }
    if(flag) answer += 10000000000 - (N-1)/3;
    flag = true;
    for (unsigned i = 0; i < N; i++){
        if(T[i] ^ (i%3 != 1)){
            flag = false;
            break;
        }
    }
    if(flag) answer += 10000000000 - N/3;
    flag = true;
    for (unsigned i = 0; i < N; i++){
        if(T[i] ^ (i%3 != 0)){
            flag = false;
            break;
        }
    }
    if(flag) answer += 10000000000 - (N+1)/3;
    printf("%llu\n", answer);
    return 0;
}