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 max_n=200005;
const int mod=998244353;
inline int Add(int x,int y){
    return (x+=y)>=mod?x-mod:x;
}
inline int Sub(int x,int y){
    return (x-=y)<0?x+mod:x;
}
inline int Mul(int x,int y){
    return 1ll*x*y%mod;
}
inline int Pow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return res;
}
int n;
char s[max_n];
int a[max_n];
int solve(int x){
    int k=n/x;
    int res=0;
    for(int i=1;i<=k;i++){
        res=Add(res,res);
        if(s[i]=='1')res=Add(res,1);
    }
    bool flag=true;
    for(int i=k+1;i<=n;i++){
        int r=(i-1)%(2*k)+1;
        int c;
        if(r<=k)c=s[r]-'0';
        else c=(s[r-k]-'0')^1;
        if(c<s[i]-'0')break;
        else if(c==s[i]-'0')continue;
        else{
            flag=false;
            break;
        }
    }
    if(flag==true)res=Add(res,1);
    return res;
}
int main(){
    scanf("%d %s",&n,s+1);
    for(int i=1;i<=n;i++){
        if(n%i||i%2==0)continue;
        a[i]=solve(i);
    }
    for(int i=n;i>=1;i--){
        for(int j=i*2;j<=n;j+=i)a[i]=Sub(a[i],a[j]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=Add(ans,Mul(n/i*2,a[i]));
    printf("%d\n",ans);
    return 0;
}