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 ll;
const int maxn=2e5+7;
const int M=998244353;
int n,a[maxn],b[maxn],ans,f[maxn];
char s[maxn];
void add(int &x,int y){x+=y; if (x>=M) x-=M;}
int calc(int d){
    int p=0;
    for (int i=0;i<d;i++) b[i]=a[i],p=(p*2+a[i])%M;
    for (int i=d;i<n;i++) b[i]=b[i-d]^1;
    bool flag=1;
    for (int i=0;i<n;i++) if (a[i]!=b[i]){
        if (a[i]<b[i]) flag=0;
        break;
    }
    if (flag) add(p,1);
    return p;
}

int main(){
    scanf("%d%s",&n,s);
    for (int i=0;i<n;i++) a[i]=s[i]-'0';
    f[1]=1; for (int i=2;i<maxn;i++) f[i]=M-1ll*(M/i)*f[M%i]%M;
    for (int i=1;i<maxn;i++) for (int j=2;j*i<maxn;j++) add(f[i*j],M-f[i]);
    for (int i=1;i<maxn;i++) if (i%2==1&&n%i==0) add(ans,1ll*f[i]*calc(n/i)%M);
    printf("%d\n",1ll*n*2*ans%M);
    return 0;
}
