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;
inline int read() {
	int x=0,f=1;
	char c=getchar();
	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
	for (;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int q=998244353;
inline int Plus(int x,int y) {return x+y>=q?(x+y-q):(x+y);}
inline int Sub(int x,int y) {return x<y?(x-y+q):(x-y);}
inline int Multi(int x,int y) {return 1ll*x*y%q;}
inline int& Pe(int &x,int y) {return x=Plus(x,y);}
inline int& Se(int &x,int y) {return x=Sub(x,y);}
inline int& Me(int &x,int y) {return x=1ll*x*y%q;}
const int maxn=2e5+10;
int n,s[maxn],b[maxn],bs=0,f[maxn];
char str[maxn];
namespace mat {
	int pw[maxn];
	void init() {
		pw[0]=1;
		for (int i=1;i<maxn;++i) pw[i]=Multi(pw[i-1],2);
	}
	int __initer__=(init(),0);
}
int get(int d) {
	int ret(0);
	for (int i=1;i<=d;++i) if (s[i]==1) Pe(ret,mat::pw[d-i]);
	static int a[maxn];
	for (int i=1;i<=d;++i) a[i]=s[i];
	for (int i=d+1;i<=n;++i) {
		a[i]=(a[i-d]^1);
		if (a[i]<s[i]) return Pe(ret,1);
		if (a[i]>s[i]) return ret;
	}
	return Pe(ret,1);
}
int main() {
	n=read();
	scanf("%s",str+1);
	for (int i=1;i<=n;++i) s[i]=str[i]-'0';
	for (int i=1;i<=n;++i) if (n%i==0 && ((n/i)&1)) b[++bs]=i;
	for (int i=1;i<=bs;++i) {
		int x=b[i];
		f[x]=get(x);
	}
	for (int i=1;i<=bs;++i) {
		int x=b[i];
		for (int j=1;j<i;++j) if (x%b[j]==0) Se(f[x],f[b[j]]);
	}
	int ans(0);
	for (int i=1;i<=bs;++i) {
		int x=b[i];
		Pe(ans,Multi(2*x,f[x]));
	}
	printf("%d\n",ans);
	return 0;
}
