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 MOD=998244353;
int add(int a,int b){
	return (a+b)%MOD;
}
int sub(int a,int b){
	return (a-b+MOD)%MOD;
}
int mul(int a,int b){
	return (LL)a*b%MOD;
}
int ksm(int a,int b){
	if(b==0){
		return 1;
	}
	else{
		int x=ksm(a,b>>1);
		return mul(mul(x,x),b&1?a:1);
	}
}
int inv(int a){
	return ksm(a,MOD-2);
}
void dadd(int &a,int b){
	a=add(a,b);
}
void dmul(int &a,int b){
	a=mul(a,b);
}
int mul(int a,int b,int c){
	return mul(mul(a,b),c);
}
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
const int N=400400;
int n,m;
char s[N];
int cnt[N];
int solve(int x){
	// cerr<<"solve "<<x<<endl;
	int g=gcd(n,x);
	int ans=0;
	int cc=1;
	for(int i=g;i>=1;i--){
		if(s[n-i]=='1'){
			// cerr<<i<<" "<<cc<<endl;
			dadd(ans,cc);
		}
		dmul(cc,2);
	}
	int l=-1;
	bool ok=true;
	for(int i=n-1;i>=n-g;i--){
		int t=n/g;
		int j=i;
		while(t--){
			int k=j%n;
			char c=s[i]^(j!=k);
			if(k>l&&c!=s[k]){
				l=k;
				ok=c<s[k];
			}
			j=(j+x)%m;
		}
		assert(j==i);
	}
	if(ok){
		dadd(ans,1);
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	scanf("%s",s);
	reverse(s,s+n);
	m=2*n;
	for(int i=1;i<=m;i++){
		if(m%i==0&&n%i!=0){
			cnt[i]=solve(i);
		}
	}
	for(int i=1;i<=m;i++){
		if(m%i!=0){
			cnt[i]=0;
		}
		// cerr<<i<<" "<<cnt[i]<<endl;
		for(int j=2*i;j<=m;j+=i){
			cnt[j]=sub(cnt[j],cnt[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		dadd(ans,mul(cnt[i],i));
	}
	printf("%d\n",ans);
	return 0;
}