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 syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
string s;

int main(){
	cin>>n>>s;
	vl a,dp;
	for(int i=1;i<=n;i++) if(n%i==0&&n/i%2==1) a.push_back(i);
	int m=a.size();
	dp=vl(m);
	for(int i=0;i<m;i++){
		int x=a[i];
		for(int j=0;j<x;j++) dp[i]=(2*dp[i]+(s[j]-'0'))%mod;
		(dp[i]+=1)%=mod;
		bool flag=0;
		for(int j=0;j<n;j++){
			char c=s[j%x];
			if(j/x%2==1){
				if(c=='1') c='0';
				else c='1';
			}
			if(c>s[j]) dp[i]=(dp[i]-1+mod)%mod;
			if(c!=s[j]) break;
		}
		for(int j=0;j<i;j++) if(x%a[j]==0&&x/a[j]%2==1) dp[i]=(dp[i]-dp[j]+mod)%mod;
	}
	ll res=0;
	for(int i=0;i<m;i++) (res+=dp[i]*a[i]*2%mod)%=mod;
	cout<<res<<endl;
}