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 <vector>
#include <string>
using namespace std;

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

    long long M = 998244353;

    vector<long long> P2(N+1);
    P2[0] = 1;
    for (int i=1; i<=N; i++)
        P2[i] = P2[i-1]*2%M;

    long long ans = 0;

    vector<long long> A(N+1);
    for (int k=1; k<=N; k++)
        if (N%k==0 && N/k%2!=0)
        {
            long long a = 0;
            for (int i=0; i<k; i++)
                if (X[i]=='1')
                    a += P2[k-i-1];
            
            string T;
            for (int i=0; i<N; i++)
                if (i/k%2==0)
                    T += X[i%k];
                else
                    T += X[i%k]^1;
            if (T<=X)
                a++;

            for (int d=1; d<k; d++)
                if (k%d==0)
                    a -= A[d];
            a = (a%M+M)%M;
            A[k] = a;

            ans += 2*k*a;
            ans %= M;
        }

    cout<<ans<<endl; 
}
