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<cstdio>

using namespace std;

const int md=998244353;
int n;
char s[200001];
char ss[200001];
int z[400001];
void cc(int w){
	for(int i=0;i<n;i++)
		if(i<w)ss[i]=s[i];
		else ss[i]=ss[i-w]^1;
	int ok=1;
	for(int i=0;i<n;i++)
		if(s[i]!=ss[i]){
			if(s[i]<ss[i])ok=0;
			break;
		}
	int ans=0;
	for(int i=0;i<w;i++){
		ans=(ans*2+(s[i]=='1'))%md;
	}
	//printf("%d %d\n",w,ans+ok);
	z[w]=ans+ok;
}
int main(){
	scanf("%d",&n);
	scanf("%s",s);
	int w=1;
	while(n%(2*w)==0)w*=2;
	for(int i=1;i*i<=n;i++)
		if(n%i==0){
			if(i&1)cc(i*w);
			if(i!=n/i&&n/i&1)cc(n/i*w);
		}
	for(int i=1;i<=n/w;i++)
		if(z[i*w])
			for(int j=i+i;j*w<=n;j+=i)
				if(j&1&&n%j==0)
					z[j*w]=(z[j*w]-z[i*w]+md)%md;
	int ans=0;
	for(int i=1;i<=n;i++){
	//	printf("%d %d\n",i,z[i]);
		if(z[i])ans=(ans+2ll*z[i]*i)%md;
	}
	printf("%d\n",ans);
}
