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;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000



int main(){
    
	int N;
	cin>>N;
	
	string S;
	cin>>S;
	
	vector<int> Y(0);
	
    for(int i=1;i<=N;i++){
		if(N%i==0&&(N/i)%2==1){
			Y.push_back(i);
		}
	}
	map<int,int> mp;
	for(int i=0;i<Y.size();i++){
		string T = S.substr(0,Y[i]);
		int a = 0;
		for(int j=0;j<T.size();j++){
			a = mod(a*2);
			if(T[j]=='1')a = mod(a+1);
		}
		string t = "";
		for(int j=0;j<T.size();j++){
			if(T[j]=='0')t+='1';
			else t+='0';
		}
		bool f = true;
		for(int j=0;j<S.size()/Y[i];j++){
			string tt = S.substr(j*Y[i],Y[i]);
			if(j%2==0){
				if(T>tt){
					f=false;
					break;
				}
				if(T<tt)break;
			}
			else{
				if(t>tt){
					f=false;
					break;
				}
				if(t<tt)break;
			}
		}
		if(f)a = mod(a+1);
		
		for(auto x:mp){
			if(Y[i]%x.first==0){
				a = mod(a - x.second);
			}
		}
		mp[Y[i]] = a;
	}
	
	int ans = 0;
	for(auto a:mp){
		int b = mod(a.first*a.second);
		ans = mod(ans+b);
	}
	
	ans=mod(ans*2);
	
	cout<<ans<<endl;
	
    
    return 0;
}

