#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mod = 998244353;

void add (int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub (int &a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
}
int mult (int a, int b)
{
    return ll(a) * b % mod;
}

void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
    int n;

    auto solve_test = [&] () {
        string x;
        cin >> x;
        assert(int(x.size()) == n);

        vector<int> mu(n + 1, +1);
        for (int i = 2; i * i <= n; i++) {
            for (int j = i * i; j <= n; j += i * i)
                mu[j] = 0;
        }

        vector<char> isprime(n + 1, 1);
        for (int i = 2; i <= n; i++) {
            if (isprime[i]) {
                for (int j = i; j <= n; j += i)
                {
                    mu[j] *= -1;
                    if (j > i)
                        isprime[j] = 0;
                }
            }
        }

        int two = 1;
        while (n % (2 * two) == 0)
            two *= 2;

        vector<vector<int>> divs(n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 2 * i; j <= n; j += i)
                divs[j].push_back(i);
        }

        auto with_blocks = [&](int l) {
            assert(n % l == 0 && (n / l) % 2 == 1);

            int ans = 0;
            for (int i = 0; i < l; i++)
                ans = mult(ans, 2), add(ans, x[i] - '0');

            bool ok = true;
            for (int i = 0; i < n; i++) {
                const char cur = ((i / l) % 2 == 0 ? x[i % l] : x[i % l] ^ '0' ^ '1');
                if (cur < x[i])
                    break;
                if (cur > x[i]) {
                    ok = false;
                    break;
                }
            }

            if (ok)
                add(ans, 1);
            return ans;
        };

        vector<int> f(n / two + 1);
        for (int i = 1; i <= n / two; i += 2) {
            if (n % i != 0)
                continue;

            f[i] = with_blocks(two * i);
            for (int j : divs[i]) {
//                if (mu[i / j] == +1)
//                    add(f[i], f[j]);
//                else if (mu[i / j] == -1)
                    sub(f[i], f[j]);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n / two; i++)
        {
            add(ans, mult(i == n / two ? 2 * n : 2 * two * i, f[i]));
        }
        return ans;
    };

    while (cin >> n)
    {
        auto res = solve_test();
        cout << res << endl;
//        break;
    }
}

void gen (stringstream &cout)
{
    mt19937 rng;
    const int n = 3000;
    const int l = int(1e9);
    cout << n << ' ' << l << endl;

    for (int i = 0; i < n; i++)
        cout << rng() % l << endl;
}

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

    cout << fixed;

#ifdef LOCAL
    //    {
//        auto st = clock();
//        stringstream test, out;
//        gen(test);
//        solve(test, out);
//        cout << "clock: " << setprecision(4) << (clock() - st) / (double) CLOCKS_PER_SEC << endl;
//        return 0;
//    }

    auto st = clock();

    ifstream fin("../input.txt");

    solve(fin);

    cout << "clock: " << setprecision(4) << (clock() - st) / (double) CLOCKS_PER_SEC << endl;
#else
    solve();
#endif

    return 0;
}

Measured memory_bytes: 23572