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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 200000
#define LL long long
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
int n,a[MAXN+5],b[MAXN+5],ans;
int pw2[MAXN+5];
char X[MAXN+5];
vector<Pr> t;
int add(int a,int b){
	return (a+b)%MOD;
}
int mul(int a,int b){
	return 1LL*a*b%MOD;
}
int sub(int a,int b){
	return (a-b+MOD)%MOD;
}
int cal(int x){
	int tmp=1;
	for(int i=1;i<=x;i++)
	b[i]=a[i],tmp=(a[i])?add(tmp,pw2[x-i]):tmp;
	for(int i=x+1;i<=n;i++)
	b[i]=b[i-x]^1;
	for(int i=1;i<=n;i++)
	if(b[i]>a[i]){tmp=sub(tmp,1);break;}
	else if(b[i]<a[i])break;
	return tmp;
}
LL read(){
	LL x=0,F=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*F;
}
int main(){
	n=read();pw2[0]=1;
	scanf("%s",X+1);
	for(int i=1;i<=n;i++){
		a[i]=(X[i]=='1');
		pw2[i]=mul(pw2[i-1],2);
	}
	for(int i=1;i<=n;i++)
	if((n%i==0)&&((n/i)%2==1)){
		int kdf=cal(i);
		for(int j=0;j<t.size();j++)
		if(i%t[j].X==0)kdf=sub(kdf,t[j].Y);
		t.push_back(Pr(i,kdf));
		ans=add(ans,mul(kdf,mul(i,2)));
	}
	printf("%d",ans);
}