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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
const ll MAX_N=2e5,MOD=998244353;
ll N;
string X;
map<ll,ll> f;
vector<ll> divv;

void cal_div(){
	for(ll i=1;i*i<=N*2;i++){
		if(2*N%i==0){
			divv.push_back(i);
			if(i*i!=2*N){
				divv.push_back(2*N/i);
			}
		}
	}
}
void cal_f(ll k){
	if(2*N/k%2==0)return;
	ll pw2=1,ans=0,sm=0;
	REP(i,k/2){
		sm+=pw2*(X[k/2-i-1]-'0');
		sm%=MOD;
		pw2*=2;
		pw2%=MOD;
	}
	ans=sm;
	string y=X.substr(0,k/2),z,x2=y;
	REP(i,k/2){
		z.push_back((1-(y[i]-'0'))+'0');
	}
	REP(i,N/k){
		x2+=z;
		x2+=y;
	}
	if(x2<=X){
		ans++;
		ans%=MOD;
	}
	f[k]=ans;
}
map<ll,ll> moe;
void cal_moe(ll n){
	vector<ll> p;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			p.push_back(i);
			while(n%i==0)n/=i;
		}
	}
	if(n!=1)p.push_back(n);
	ll m=p.size();
	REP(i,1<<m){
		ll mo=1,d=1;
		REP(j,m){
			if((i>>j)&1){
				mo*=-1;
				d*=p[j];
			}
		}
		moe[d]=mo;
	}
}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>X;
	cal_div();
	for(auto i:divv){
		cal_f(i);
	}
	cal_moe(2*N);
	ll ans=0;
	for(auto n:divv){
		ll g=0;
		for(auto d:divv){
			if(n%d==0){
				g+=moe[n/d]*f[d]+MOD;
				g%=MOD;
			}
		}
//		cout<<"g["<<n<<"]="<<g<<endl;
		ans+=g*n;
		ans%=MOD;
	}
	cout<<ans<<endl;
	for(auto n:divv){
//		cout<<"f["<<n<<"]="<<f[n]<<endl;
	}
}