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 lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	inline int ts(char *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		s[a]=0;
		return a;
	}
}
using ae86::ty;
using ae86::ts;

const int _ = 200007 , mo = 998244353;

int n;char s[_],t[_];
lint f[_]={0};

int main()
{
	n=ty(),ts(s+1);
	for(int i=1;i<=n;i++)s[i]-=48;
	
	for(int i=1;i<=n;i++)
	{
		if(n%i!=0 || (n/i)%2!=1)continue;

		lint val=0;
		for(int j=1;j<=i;j++)t[j]=s[j],val=(val*2+t[j])%mo;
		val=(val+1)%mo;
		for(int j=i+1;j<=n;j++)t[j]=t[j-i]^1;
		for(int j=1;j<=n;j++){if(s[j]==t[j])continue;if(s[j]<t[j])val=(val-1+mo)%mo;break;}
		f[i]=(f[i]+val)%mo;
	}
	lint ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!f[i] || n%i!=0 || (n/i)%2!=1)continue;
		for(int j=i+i;j<=n;j+=i)f[j]=(f[j]-f[i]+mo)%mo;
		ans=(ans+2ll*i*f[i]%mo)%mo;
	}

	printf("%lld\n",ans);

	return 0;
}

