#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
#include <cstdint>
using namespace std;
using LL = long long;

//負数の合同も考慮に入れるmod関数
inline long long imod(long long a, long long b)
{
	return (a >= 0) ? (a % b) : (a % b + b);
}

//mintが引数の繰り返し2乗法
class mint;
mint pow(mint x, long long n);

//modの整数クラス
class mint
{
public:
	static void set_mod(long long m_)
	{
		//無効な値は無視
		if (m_ < 2)return;
		//modの値を更新
		mod = m_;
		//オイラー関数Φ(mod)を計算する
		e_phi = m_;
		for (int i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				e_phi = e_phi / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)e_phi = e_phi / m_ * (m_ - 1);
	}
	mint operator+(const mint& other)const
	{
		return mint(a + other.a >= mod ? a + other.a - mod : a + other.a, true);
	}
	mint operator-(const mint& other)const
	{
		return mint(a - other.a < 0 ? a - other.a + mod : a - other.a, true);
	}
	mint operator*(const mint& other)const
	{
		return mint(imod(a * other.a, mod));
	}
	mint operator+=(const mint& other)
	{
		a = a + other.a >= mod ? a + other.a - mod : a + other.a;
		return mint(a, true);
	}
	mint operator-=(const mint& other)
	{
		a = a - other.a < 0 ? a - other.a + mod : a - other.a;
		return mint(a, true);
	}
	mint operator*=(const mint& other)
	{
		a = imod(a * other.a, mod);
		return mint(a);
	}
	mint operator+()const
	{
		return *this;
	}
	mint operator-()const
	{
		return mint(mod - a >= mod ? -a : mod - a, true);
	}
	mint& operator++()
	{
		*this += 1;
		return *this;
	}
	mint operator++(int)
	{
		auto tmp = *this;
		*this += 1;
		return tmp;
	}
	mint& operator--()
	{
		*this -= 1;
		return *this;
	}
	mint operator--(int)
	{
		auto tmp = *this;
		*this -= 1;
		return tmp;
	}
	mint operator~()const
	{
		return pow(*this, e_phi - 1);
	}
	mint& operator=(const mint& other)
	{
		a = other.a;
		return *this;
	}
	operator long long()const
	{
		return a;
	}
	explicit operator int()const
	{
		return (int)a;
	}
	static long long getmod()
	{
		return mod;
	}
	mint(long long a_) :a(imod(a_, mod)) {}
	mint() :a(0) {}
private:
	static long long mod;
	static long long e_phi;
	long long a;
	mint(long long a_, bool) : a(a_) {}
};

//mintの累乗
//x^nを計算します
mint pow(mint x, long long n)
{
	mint res = 1;
	while (n > 0)
	{
		if (n & 1)res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

#include <vector>
mint minv[3333];

//mintの階乗計算
//O(x)程度の時間がかかります
//非推奨、同時間でfact_setが計算可能
mint fact(mint x)
{
	mint res(1);
	for (long long i = 1; i <= (long long)x; ++i)
	{
		res *= i;
	}
	return res;
}

//mintの階乗計算のリスト
//setの末尾に0～xまでの階乗数の列挙をします
//O(x)程度の時間がかかります
void fact_set(std::vector<mint>& set, mint x = mint(-1))
{
	mint res(1);
	set.push_back(1);
	for (long long i = 1; i <= (long long)x; ++i)
	{
		res *= i;
		set.push_back(res);
	}
}

long long mint::mod = 998244353;
long long mint::e_phi = mod - 1;

#include<iostream>

//mint型のstreamへの入出力対応
std::ostream& operator<<(std::ostream& os, mint i)
{
	os << (long long)i;
	return os;
}

std::istream& operator >> (std::istream& is, mint& i)
{
	long long tmp;
	is >> tmp;
	i = tmp;
	return is;
}

using Poly = vector<mint>;

Poly operator*(const Poly& p1, const Poly& p2) {
	Poly res(p1.size() + p2.size() - 1);
	for (int j = 0; j < p2.size(); ++j) {
		for (int i = 0; i < p1.size(); ++i) {
			res[i + j] += p1[i] * p2[j];
		}
	}
	return res;
}

Poly operator/(const Poly& p1, const Poly& p2) {
	Poly p3 = p1;
	Poly res(p1.size() + 1 - p2.size());
	for (int i = res.size() - 1; i >= 0; --i) {
		res[i] = p3[p2.size() - 1 + i] * minv[p2[p2.size() - 1]];
		for (int j = i; j < i + p2.size(); ++j) {
			p3[j] -= res[i] * p2[j - i];
		}
	}
	return res;
}

mint calc(const Poly& pol, mint x) {
	mint ans = 0;
	mint tak = 1;
	for (int i = 0; i < pol.size(); ++i) {
		ans += tak * pol[i];
		tak *= x;
	}
	return ans;
}

LL N;
string X, Y;
mint imos[234567];
mint two[234567];
mint opt[234567];
mint shsh[234567];
mint hshs[234567];

mint solve(int k) {
	mint res = imos[k];
	bool flag = true;
	for (int g = 1; g < N / k; ++g) {
		LL now = shsh[g * k + k] - shsh[g * k] * opt[k];
		if (g % 2 == 1) {
			now = hshs[g * k + k] - hshs[g * k] * opt[k];
		}
		if (now == shsh[k]) {
			continue;
		}
		else {
			if (g % 2 == 1) {
				for (int i = 0; i < k; ++i) {
					if (X[i + k * g] > Y[i]) {
						break;
					}
					else if (X[i + k * g] < Y[i]) {
						flag = false;
						break;
					}
				}
			}
			else {
				for (int i = 0; i < k; ++i) {
					if (X[i + k * g] > X[i]) {
						break;
					}
					else if (X[i + k * g] < X[i]) {
						flag = false;
						break;
					}
				}
			}
			break;
		}
	}
	if (flag)res++;
	return res;
}

int main() {
	cin >> N >> X;
	Y.resize(N);
	for (int i = 0; i < N; ++i) {
		imos[i + 1] = imos[i] + imos[i];
		shsh[i + 1] = shsh[i] * mint(1000003);
		hshs[i + 1] = hshs[i] * mint(1000003);
		shsh[i + 1] += X[i];
		if (X[i] == '1') {
			imos[i + 1]++;
			Y[i] = '0';
		}
		else {
			Y[i] = '1';
		}
		hshs[i + 1] += Y[i];
	}
	two[0] = 1;
	opt[0] = 1;
	for (int i = 0; i <= N; ++i) {
		two[i + 1] = two[i] + two[i];
		opt[i + 1] = opt[i] * mint(1000003);
	}
	vector<int>yak;
	for (int i = 1; i <= N; ++i) {
		if (N % i == 0) {
			yak.push_back(i);
		}
	}
	map<int, mint>dp;
	map<int, vector<int>>to;
	for (int elm : yak) {
		int pack = N / elm;
		if (pack % 2 == 0) {
			continue;
		}
		for (int i = pack + pack; i <= N; i += pack) {
			if (N % i == 0)
				if (i % 2 == 1)
					to[i].push_back(pack);
		}
	}
	for (int elm : yak) {
		int pack = N / elm;
		if (pack % 2 == 0) {
			continue;
		}
		if (elm != N)
			dp[pack] = solve(elm);
		else
			dp[pack] = imos[elm] + mint(1);
	}
	//reverse(yak.begin(), yak.end());
	mint ans = 0;
	for (int x : yak) {
		int pack = N / x;
		if (pack % 2 == 0) {
			continue;
		}
		//ans += dp[pack];
		for (int t : to[pack]) {
			dp[t] -= dp[pack];
		}
	}
	for (auto p : dp) {
		ans += p.second * mint(N / p.first) * mint(2);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9988