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"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    string X;
    cin >> N >> X;

    constexpr ll MOD = 998244353;

    string S = X;
    for (char x : X) {
        S += (x == '0' ? '1' : '0');
    }

    //Sはb ~b b ~b ... b ~b みたいな列（の操作途中の列）であれば2 * |b|でループする
    //つまりループの周期をtとしたとき、tは偶数
    //当然tは2 * Nの約数である必要もあり、またXがb ~b bという形になるため2 * N / tは奇数でないといけない

    ll ans = 0;
    map<ll, ll> num;
    //周期としてあり得るものが列挙できた
    for (ll t = 1; t <= 2 * N; t++) {
        if (2 * N % t != 0 || t % 2 == 1 || (2 * N / t) % 2 == 0) {
            continue;
        }

        //周期の半分bitを考える
        //Sの先頭t / 2 bitと比較して小さいものだけ数える
        ll small = 0;
        for (ll i = 0; i < t / 2; i++) {
            (small = 2 * small + (S[i] == '1')) %= MOD;
        }

        ll n = small;

        //equalだけ愚直に構築して調べる
        string sub = S.substr(0, t / 2);
        string sub_rev = sub;
        for (char& c : sub_rev) {
            c = (c == '0' ? '1' : '0');
        }
        string str;
        for (ll i = 0; i < 2 * N / (t / 2); i++) {
            str += (i % 2 == 0 ? sub : sub_rev);
        }
        if (str <= S) {
            n++;
        }

        //包除
        for (ll i = 2; i * i <= t; i++) {
            if (t % i == 0) {
                (n += MOD - num[i]) %= MOD;

                if (i * i != t) {
                    (n += MOD - num[t / i]) %= MOD;
                }
            }
        }

        num[t] = n;
        (ans += n * t) %= MOD;
    }

    cout << ans << endl;
}