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;

const int MOD = 998244353, N = 200005;

int n;
string s;
long long ans = 0, cnt[N];
vector<int> ve;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 1; i <= n; i += 2) {
        if (n % i == 0) {
            ve.push_back(i);
        }
    }
    reverse(ve.begin(), ve.end());
    for (int &u : ve) {
        int len = n / u;
        for (int i = 0; i < len; i++) {
            ((cnt[u] *= 2) += s[i] - '0') %= MOD;
        }
        cnt[u]++;
        for (int i = 0; i < n; i++) {
            char c = s[i % len];
            if ((i / len) & 1) {
                c ^= '0' ^ '1';
            }
            if (c > s[i]) {
                cnt[u]--;
                break;
            } else if (c < s[i]) {
                break;
            }
        }
        for (int &v : ve) {
            if (v > u && v % u == 0) {
                (cnt[u] -= cnt[v]) %= MOD;
            }
        }
        (ans += cnt[u] * len) %= MOD;
    }
    cout << ((ans + MOD) * 2) % MOD;
}
