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"
#include<valarray>

using namespace std;

#define MAX 200002

int n;
int x;

char buf[MAX];
string s;
string t;

vector<pair<int,long long int> > v;

#define MOD 998244353

long long int p2[MAX];


int main(){
	cin>>n;
	scanf("%s",buf);
	s=buf;
	for(int i=0;i<n;i++){
		//cout<<s<<endl;
		s.push_back('1'-s[i]+'0');
	}
	//cout<<s<<endl;
	t=s;
	p2[0]=1;
	for(int i=1;i<MAX;i++){
		p2[i]=p2[i-1]*2;
		p2[i]%=MOD;
	}
	for(int i=1;i<=2*n;i++){
		if(2*n%i)continue;
		int num=(2*n)/i;
		if(num%2==0)continue;
		int len=i/2;
		long long int ans=0;
		for(int j=0;j<len;j++){
			if(s[j]=='1'){
				ans+=p2[len-j-1];
			//	cout<<len<<" "<<ans<<" "<<p2[len-j-1]<<endl;
				if(ans>=MOD)ans%=MOD;
			}
		}
		for(int j=0;j<2*n;j++){
			int rep=j/len;
			rep%=2;
			int att=j%len;
			if(rep==0){
				t[j]=s[att];
			}
			else{
				t[j]='1'-s[att]+'0';
			}
		}
	//	cout<<s<<" "<<t<<endl;
		if(s>=t){
			ans++;
		}
		if(ans>=MOD)ans%=MOD;
		v.push_back(make_pair(len,ans));
		//cout<<len<<" "<<ans<<endl;
	}
	long long int ans=0;
	for(int i=0;i<v.size();i++){
		for(int j=i+1;j<v.size();j++){
			if(v[j].first%v[i].first==0LL){
				v[j].second+=MOD-v[i].second;
				v[j].second%=MOD;
			}
		}
		ans+=v[i].first*(long long int)v[i].second;
		ans%=MOD;
	}
	ans*=2LL;
	ans%=MOD;
	printf("%lld\n",ans);
	return 0;
}
