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;
typedef long long ll;
const ll mod=998244353;
int n;
ll cnt=0;
ll ans=0,c1=0,c2=0;
ll f[200001];
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	string s;cin >> s;
	for(int i=1; i<n ;i++){
		if(n%i==0 && n/i%2==1) f[i]=2*i-2*n;
	}
	for(int i=n-1; i>=1 ;i--){
		if(f[i]==0) continue;
		for(int j=2*i; j<n ;j+=i){
			f[i]=(f[i]+mod-f[j])%mod;
		}
	}
	for(int i=1; i<n ;i++){
		if(f[i]!=0){
			string t="";
			for(int j=0; j<n ;j++){
				char c=((j/i%2)^s[j%i]);
				if(j==n-1 && c==s[j]) ans+=f[i];
				if(c==s[j]) continue;
				if(c<s[j]) ans+=f[i];
				break;
			}
			c1=c2=0;
			for(int j=0; j<i ;j++){
				c1=c1*2+s[j]-48;
				c1%=mod;
			}
			ans=(ans+c1*f[i])%mod;
			ans=(ans+mod)%mod;
		}
	}
	c1=s[n-1]-48+1;
	c2=2;
	for(int i=n-2; i>=0 ;i--){
		if(s[i]=='1') c1=(c1+c2)%mod;
		c2=(c2+c2)%mod;
	}
	c1=c1*2*n%mod;
	ans=(ans+c1)%mod;
	ans=(ans+mod)%mod;
	cout << ans << endl;
}