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 <iostream>
#include <string>
#include <map>
#include <algorithm>

int64_t mod = 998244353;

std::string neg(std::string bits)
{
    for (char& c : bits) c = c=='1'?'0':'1';
    return bits;
}

int64_t pass(const std::string& bits, int k)
{
    std::string a = bits.substr(0, k);
    std::string b = neg(a);
    std::string pattern = a;
    for (int i=k;i<bits.length();i+=2*k)
    {
        pattern += b;
        pattern += a;
    }
    return pattern <= bits ? 1 : 0;
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    int n;
    std::cin >> n;
    std::string bits;
    std::cin >> bits;
    std::reverse(bits.begin(), bits.end());
    while (bits.size() < n) bits.push_back('0');
    std::reverse(bits.begin(), bits.end());

    int64_t result = 0;
    int64_t pref = 0;
    std::map<int, int64_t> S;
    for (int l=1;l<=n;++l)
    {
        pref *= 2;
        pref += bits[l-1] == '1' ? 1 : 0;
        pref %= mod;

        if (n % l == 0 && (n/l) & 1)
        {
            auto& s = S[l];
            s = (pref + pass(bits, l)) % mod;
            for (auto it : S)
            {
                int k = it.first;
                if (k < l && l % k == 0) s = (s + mod - it.second) % mod;
            }
            result = (result+2*s*l) % mod;
        }
    }

    std::cout << result;

    return 0;
}
