#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

#define mkp make_pair
#define mkt make_tuple
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
template <class T>
void chmin(T &a, const T &b) {
    if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
    if (a < b) a = b;
}

void add(ll &a, ll b) {
    a = (a + b) % MOD;
}

void mul(ll &a, ll b) {
    a %= MOD;
    b %= MOD;
    a = a * b % MOD;
}

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<vector<vector<int>>> idxs(N + 1, vector<vector<int>>(N + 1));
    for (int k = 1; k <= N; k++) {
        ll sum = 0;
        idxs[k][0].push_back(0);
        for (int i = 0; i < N; i++) {
            sum += A[i];
            sum %= k;
            idxs[k][sum].push_back(i + 1);
        }
    }

    vector<vector<int>> nxt(N + 1, vector<int>(N + 1, -1));
    for (int k = 1; k <= N; k++) {
        for (int rest = 0; rest < k; rest++) {
            for (int j = 0; j + 1 < idxs[k][rest].size(); j++) {
                nxt[idxs[k][rest][j]][k] = idxs[k][rest][j + 1];
            }
        }
    }

    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, -1));
    auto rec = [&](auto &&rec, int now, int divisor) -> ll {
        if (now == N) return 1;
        if (dp[now][divisor] != -1) return dp[now][divisor];

        ll sum = 0;
        ll res = 0;
        if (nxt[now][divisor] != -1) {
            add(res, rec(rec, nxt[now][divisor], divisor));
            if (nxt[now][divisor] < N) add(res, rec(rec, nxt[now][divisor], divisor + 1));
        }

        return dp[now][divisor] = res;
    };

    ll ans = rec(rec, 0, 1);
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();

    return 0;
}
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i,0,n)
#define BFOR(bit,a,b) for(int bit = (a); bit < (1<<(b)); ++bit)
#define BREP(bit,n) BFOR(bit,0,n)
using namespace std;
using ll = long long;

int main() {
    ll n;
    string t;
    cin >> n >> t;
    if(t == "1"){
        ll ans = 1e10 * 2;
        cout << ans << endl;
        return 0;
    }
    if(t == "0"){
        ll ans = 1e10;
        cout << ans << endl;
        return 0;
    }
  	if(t == "00"){
        ll ans = 0;
        cout << ans << endl;
        return 0;
    }
  	if(t == "10"){
        ll ans = 1e10;
        cout << ans << endl;
        return 0;
    }
  	if(t == "01"){
        ll ans = 1e10-1;
        cout << ans << endl;
        return 0;
    }
    if(t == "11"){
        ll ans = 1e10;
        cout << ans << endl;
        return 0;
    }
  	if(t[0] != '1' || t[1] != '1' || t[2] != '0'){
      if(t[0] == '1' && t[1] == '0'){
        t = "1"+t;
        n++;
      }
      else if(t[0] == '0'){
        t = "11"+t;
        n += 2;
      }
      else{
        cout << 0 << endl;
      	return 0;
      }
    }
    if(t[n-3] != '1' || t[n-2] != '1' || t[n-1] != '0'){
      if(t[n-1] == '1' && t[n-2] == '1'){
        t = t+"0";
        n++;
      }
      else if(t[n-1] == '1'){
        t = t+"10";
        n += 2;
      }
    }
  	if(n % 3 != 0){
      cout << 0 << endl;
      return 0;
    }
  	string s;
  	REP(i,n/3) s += "110";
    ll ans;
  	if(s == t) ans = 1e10 - n/3+1;
    else ans = 0;
    cout << ans << endl;
}