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
/*====Corycle====*/
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int Mod=998244353;
const int N=4e5+5;
int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*f;
}
char s[N];
int n,m,Ans,a[N],b[N],f[N];
int mod(int x){return x>=Mod?x-Mod:x;}
int Solve(int T){
	int L=T/2,ans=0,flag=1;
	for(int i=1;i<=L;i++){ans=mod(ans*2+a[i]);b[i]=a[i];}
	for(int i=L+1;i<=n;i++)b[i]=a[i-L]^1;
	for(int i=1;i<=n;i++){
		if(b[i]<a[i])break;
		if(b[i]>a[i]){flag=0;break;}
	}
	ans=mod(ans+flag);
	return f[T]=ans;
}
int main(){
//	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	n=read();scanf("%s",s+1);
	for(int i=1;i<=n;i++)a[i]=s[i]-'0';
	for(int i=1;i<=n*2;i++)if(n%i!=0&&n*2%i==0)Solve(i);
	for(int i=1;i<=n*2;i++){
		if(!(n%i!=0&&n*2%i==0))continue;
		for(int j=i*2;j<=n*2;j+=i){
			if(!(n%j!=0&&n*2%j==0))continue;
			f[j]=mod(f[j]-f[i]+Mod);
		}
	}
	for(int i=1;i<=n*2;i++)Ans=mod(Ans+1ll*f[i]*i%Mod);
	printf("%d\n",Ans);
	return 0;
}