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 maxn=4e5+10;

namespace Calc_with_MOD{
	const int mod=998244353;
	int add(ll a,ll b){
		ll ret=a+b;
		if(ret<=0)ret+=mod;
		ret%=mod;
		return ret;
	}
	int dec(ll a,ll b){
		ll ret=a-b;
		ret%=mod;
		if(ret<=0)ret+=mod;
		ret%=mod;
		return ret;
	}
	int mul(ll a,ll b){
		a%=mod;b%=mod;
		ll ret=a*b%mod;
		if(ret<=0)ret+=mod;
		return ret;
	}
}
int n,ans,a[maxn];
char s[maxn];
using namespace Calc_with_MOD;
int calc(int x){
	int k=n/x,res=0;
	for(int i=1;i<=k;++i){
		res=add(res,res);
		if(s[i]=='1')res=add(res,1);
	}
	int flag=1;
	for(int i=k+1;i<=n;++i){
		int r=(i-1)%(2*k)+1,c;
		if(r<=k)c=s[r]-'0';
		else c=s[r-k]-'0',c^=1;
		
		if(c<s[i]-'0')break;//if T is lexicographically less than T'
		else if(c==s[i]-'0')continue;//continue for compare
		else {flag=0;break;} //not satisfy
	}

	res+=flag;
	return res;
}
void solve(){
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;++i){
		if(n%i||~i&1)continue;
		a[i]=calc(i);
	}
	for(int i=n;i;--i)
		for(int j=i+i;j<=n;j+=i)
			a[i]=dec(a[i],a[j]);
	int res=0;
	for(int i=1;i<=n;++i)
		res=add(res,mul(n/i*2,a[i]));
	printf("%d\n",res);
}
int main(){
	solve();

	return 0;
}
//powered by poorwill