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 rep(i,n)for(int i=0;i<(n);i++)
using namespace std;                                      
typedef long long ll;
typedef pair<int,int>P;

const int MOD=998244353;

ll ppow(ll a,ll b){
	a%=MOD;
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

vector<ll>divisor(ll n){
	vector<ll>res;
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			res.push_back(i);
			if(i!=n/i)res.push_back(n/i);
		}
	}
	return res;
}

ll dp[500000];

int main(){
	int n;string s;cin>>n>>s;
	auto v=divisor(n);
	for(int k:v){
		if((n/k)%2==0)continue;
		ll sum=0;
		rep(i,k){
			if(s[i]=='1')(sum+=ppow(2,k-i-1))%=MOD;
		}
		int g=0;
		bool ok=false;
		while(g<n){
			char c=s[g%k];
			if((g/k)%2==1)c=(c=='0'?'1':'0');
			if(s[g]==c)g++;
			else{
				if(s[g]<c)ok=false;
				else ok=true;
				break;
			}
		}
		if(g==n||ok)sum++;
		dp[k]=sum%MOD;
	}
	for(int i=1;i<=n;i++){
		if(!dp[i])continue;
		for(int j=2*i;j<=n;j+=i)(dp[j]+=MOD-dp[i])%=MOD;
	}
	ll all=1;
	rep(i,n){
		if(s[i]=='1')(all+=ppow(2,n-i-1))%=MOD;
	}
	ll ans=0;
	for(int k:v){
		(ans+=2*k*dp[k])%=MOD;
		(all+=MOD-dp[k])%=MOD;
	}
	(ans+=all*2*n)%=MOD;
	cout<<ans<<endl;
}