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 ll long long
#define ld long double
#define ull unsgned ll
#define db double
#define pint pair<int,int>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=4e5+5,Mod=998244353;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
//inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,a[MAXN],b[MAXN],f[MAXN],ans;char s[MAXN];
inline void Solve(int k){
	int res=0;
	Rep(i,1,k/2)res=(res<<1|a[i])%Mod,b[i]=a[i],b[i+k/2]=!a[i];
	int flg=0;
	Rep(i,1,2*n)if(a[i]!=b[(i-1)%k+1]){flg=a[i]<b[(i-1)%k+1];break;}
	f[k]=(res-flg+1)%Mod;
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),scanf("%s",s+1);Rep(i,1,n)a[i]=s[i]^48,a[i+n]=!a[i];
	Rep(i,1,2*n)if(n%i&&2*n%i==0)Solve(i);
	Rep(i,1,2*n)if(n%i&&2*n%i==0)for(int j=i+i;j<=2*n;j+=i)if(n%j&&2*n%j==0)f[j]=(f[j]-f[i]+Mod)%Mod;
	Rep(i,1,2*n)if(n%i&&2*n%i==0)ans=(ans+1ll*f[i]*i)%Mod;cout<<ans<<'\n';
	return 0;
}



