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;
typedef long long i64;
const int N = 4e5+5, P = 998244353;
int n, f[N], s[N], ans; char X[N], Y[N]; void fix(int &x) { x<P?0:x-=P; }
int G(int T)
{
    for(int i = 1, j = 0; i <= n; i += T>>1, j ^= 1) for(int k = 0; k < T>>1; ++k) Y[i+k] = X[k+1]^j;
    bool flg = true; for(int i = 1; i <= n&&flg; ++i) if(X[i] < Y[i]) flg = false; else if(X[i] > Y[i]) break;
    return s[T>>1]+flg;
}
int main()
{
    scanf("%d%s", &n, X+1);
    for(int i = 1; i <= n; ++i) X[i] -= '0', fix(s[i]=s[i-1]<<1|X[i]);
    for(int i = 1; i <= 2*n; ++i) if((2*n)%i == 0&&n%i != 0) f[i] = G(i);
    for(int i = 2; i <= n<<1; i += 2) if(f[i]) for(int j = i<<1; j <= n<<1; j += i) 
        if((2*n)%j == 0&&n%j != 0) fix(f[j]+=P-f[i]);
    for(int i = 2; i <= n<<1; i += 2) if(f[i]) fix(ans += (i64)f[i]*i%P);
    printf("%d\n", ans);
    return 0;
}