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 pb push_back
#define mp make_pair
#define int long long
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
int hik[214514];
vector<int> dv[214514];
int n;
string s;
int counter( int k ){
	int res = 0;
	int num = n/k;
	string gen = s.substr(0,k);
	string gak;
	for(int i=0;i<k;i++){
		if(gen[i]=='0')gak.pb('1');
		else gak.pb('0');
	}
	bool fl = true;
	string cur;
	for(int i=1;i<num;i++){
		cur = s.substr(i*k,k);
		if( i % 2 == 0){
			if( gen > cur ){
				fl = false;
				break;
			}
			else if( gen < cur ){
				fl = true;
				break;
			}
		}
		else{
			if( gak > cur ){
				fl = false;
				break;
			}
			else if( gak < cur ){
				fl = true;
				break;
			}
		}
	}
	for(int i=0;i<k;i++){
		res*=2;
		if(gen[i]=='1')res++;
		res %= inf;
	}
	if( fl == true ) res++;
	res %= inf;
	return res;
}
signed main(){
	cin>>n;
	cin>>s;
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			dv[j].pb(i);
		}
	}
	for(int i=1; i<=n; i++){
		if( n % i == 0 && (n/i)%2 == 1 ){
			int res = counter(i);
			for(int j=0;j<dv[i].size();j++){
				res = res + inf - hik[ dv[i][j] ];
				res %= inf;
			}
			//cout<<i<<" "<<res<<endl;
			ans += 2 * i * res;
			ans %= inf;
			hik[i] = res;
		}
	}
	cout<<ans<<endl;
	return 0;
}