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;

const int mod = 998244353;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	long long int tot = 0;
	for(auto it:s){
		tot<<=1;
		if(it == '1')	tot++;
		tot%=mod;
	}
	tot++;
	vector<pair<int,long long int> > v;
	for(int len=1;len<=n;len++)
		if(n*2%len==0){
			int block=n*2/len;
			if(block%2==0)	continue;
			long long int cur = 0;
			string cs;
			for(int i=0;i<n;i++)
				if(i/(len/2)%2==0)
					cs+=s[i%(len/2)];
				else
					cs+=char('1'+'0'-s[i%(len/2)]);
			for(int i=0;i<len/2;i++){
				cur<<=1;
				if(s[i]=='1')	cur++;
				cur%=mod;
			}
			cur++;
			if(cs>s)	cur--;
			for(auto it:v)
				if(len%it.first==0)
					cur-=it.second;
			cur=(cur%mod+mod)%mod;
			v.emplace_back(len,cur);
		}
	long long int ans=0;
	for(auto it:v)
		tot-=it.second,ans=(ans+it.first*it.second)%mod;
	ans+=tot%mod*2*n%mod;
	ans=(ans%mod+mod)%mod;
	cout<<ans<<endl;
}
