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>
#define int long long
const int mu=998244353,N=200005;
int f[N],s[N],b[N];
char t[N],c[N];
int n,k,ans;
void count(int x){
	for (int i=1;i<=x;i++)
		f[x]=(f[x]*2ll+s[i])%mu;
	f[x]++;
	for (int i=1;i<=n/x;i++){
		if (i&1){
			for (int j=(i-1)*x+1;j<=i*x;j++) b[j]=s[(j-1)%x+1];	
		}
		else for (int j=(i-1)*x+1;j<=i*x;j++) b[j]=s[(j-1)%x+1]^1;
	}
	for (int i=1;i<=n;i++){
		if (b[i]<s[i]) break;
		if (b[i]>s[i]){
			f[x]--;
			break;
		}
	}
	f[x]=(f[x]+mu)%mu; 
	for (int i=1;i<x;i++)
		if (x%i==0) f[x]=(f[x]-f[i]+mu)%mu;	
}
signed main(){
	scanf("%lld",&n);
	scanf("%s",t+1);
	for (int i=1;i<=n;i++) s[i]=t[i]-'0';
	for (int i=1;i<=n;i++)
		if (n%i==0 && (n/i)&1) 
			count(i);
	for (int i=1;i<=n;i++)
		if (n%i==0 && (n/i)&1) ans=(ans+f[i]*2ll*i)%mu;
	printf("%lld\n",ans);
}