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>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
using namespace std;
const int N=2e5+5,mo=998244353;
int n,_[N],v[N],mu[N],p[N],ps;
char c[N];
ll ans,tot;
bool b[N];
int main(){
	scanf("%d\n",&n);
	fo(i,2,n){
		if(!b[i])p[++ps]=i,mu[i]=-1;
		for(int j=1,u;(u=i*p[j])<=n;++j){
			b[u]=1;
			if(i%p[j]==0)break;
			mu[u]=-mu[i];
		}
	}
	_[0]=1;
	fo(i,1,n)c[i]=getchar()-'0',tot=(tot*2+c[i])%mo;
	tot=(tot+1)%mo;
	fo(i,1,n-1)if(n%i==0&&(n/i)&1){
		ll tt=0;
		fo(j,1,i)tt=(tt*2+c[j])%mo;
		bool is=1;
		fo(j,i+1,n){
			bool a=c[(j-1)%i+1]^(((j-1)/i)&1);
			if(a==c[j])continue;
			if(a<c[j]){
				is=1;break;
			}
			is=0;break;
		}
		fo(j,1,i-1)if(i%j==0&&((i/j)&1)){
			tt=((ll)tt+mo-v[j])%mo;
		}
		tt=(tt+is)%mo;
		v[i]=tt;
		tot=(tot+mo-tt)%mo;
		ans=(ans+(ll)tt*i*2)%mo;
	}
	cout<<(ans+tot*n*2)%mo;
}