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 i64 = long long;

int main() {
    constexpr i64 mod = 998244353;
    int n;
    std::string s;
    std::cin >> n >> s;

    i64 c = 0, ret = 0;
    std::vector<std::pair<int, i64>> memo;
    for (int i = 0; i < n; i++) {
        c = (c * 2 + (s[i] == '1')) % mod;

        int d = i + 1;
        if (n % d || n / d % 2 == 0) continue;

        i64 overlap = 0;
        for (auto &e : memo) if (d % e.first == 0 && d / e.first % 2) overlap = (overlap + e.second) % mod;

        int flg = 1;
        for (int j = 0; j < n; j++) {
            int k = j / d % 2 ? '0' + '1' - s[j % d] : s[j % d];
            if (s[j] == k) continue;
            flg = k < s[j];
            break;
        }

        i64 count = (c + flg + mod - overlap) % mod;
        memo.emplace_back(d, count);
        ret = (ret + count * d % mod * 2 % mod) % mod;
    }

    std::cout << ret << std::endl;

    return 0;
}
