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
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MN = 200002;
constexpr ll MOD = 998244353;

vector<int> divisors(int n) {
    vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i) continue;
        ret.push_back(i);
        if (i*i < n) ret.push_back(n/i);
    }
    sort(begin(ret), end(ret));
    return ret;
}

int val(string & s) {
    int res = 0;
    for (char c : s) ((res <<= 1) += c == '1') %= MOD;
    return res;
}

void inv(string & s) { for (char & c : s) c = '0'+'1'-c; }

int cnt[MN];

int main() {
    if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N; string X; cin >> N >> X;

    int ans = 0;
    for (int d : divisors(N)) {
        int m = N/d;
        if (m%2 == 0) continue;
        string s = X.substr(0, d);
        (cnt[d] += val(s)) %= MOD;

        string t, r = s; inv(r);
        for (int i = 0; i < m; ++i) i%2 == 0 ? t += s : t += r;
        if (t <= X) ++cnt[d] %= MOD;

        for (int j = 2*d; j <= N; j += d) if (N%j == 0) (cnt[j] += MOD-cnt[d]) %= MOD;
        (ans += 2ll*d*cnt[d]%MOD) %= MOD;
    }
    cout << ans;
}
