Given are integers N and X. For each integer k between 0 and X (inclusive), find the answer to the following question, then compute the sum of all those answers, modulo 998244353.

* Let us repeat the following operation on the integer k. Operation: if the integer is currently odd, subtract 1 from it and divide it by 2; otherwise, divide it by 2 and add 2^{N-1} to it. How many operations need to be performed until k returns to its original value? (The answer is considered to be 0 if k never returns to its original value.)

Constraints

* 1 \leq N \leq 2\times 10^5
* 0 \leq X < 2^N
* X is given in binary and has exactly N digits. (In case X has less than N digits, it is given with leading zeroes.)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
X


Output

Print the sum of the answers to the questions for the integers between 0 and X (inclusive), modulo 998244353.

Examples

Input

3
111


Output

40


Input

6
110101


Output

616


Input

30
001110011011011101010111011100


Output

549320998
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const ll MOD = 998244353;

int n;
string s;

char rev(char x) {
    if (x == '0') {
        return '1';
    } else {
        return '0';
    }
}

string t;

const int N = 210000;
ll dp[N];

ll ans = 0;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
    cin >> n;
    cin >> s;
    for (int k = 1; k <= n; ++k) {
        if (n % k != 0 || (n / k) % 2 == 0) {
            continue;
        }
        ll go = 0;
        for (int i = 0; i < k; ++i) {
            go = (go * 2 + (s[i] == '1')) % MOD;
        }
        t = "";
        int g = n / k;
        for (int i = 0; i < g; ++i) {
            for (int j = 0; j < k; ++j) {
                if (i % 2 == 0) {
                    t += s[j];
                } else {
                    t += rev(s[j]);
                }
            }
        }
        if (t <= s) {
            go = (go + 1) % MOD;
        }
        dp[k] = (dp[k] + go) % MOD;
        ans = (ans + 2 * k * dp[k]) % MOD;
        for (int i = 2 * k; i <= n; i += k) {
            dp[i] = (dp[i] - dp[k] + MOD) % MOD;
        }
    }
    cout << ans << "\n";
	return 0;
}


