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 int N = 5e5+100, MOD = 998244353;

int add(ll a, int b){
	return (a + b + 2LL*MOD) % MOD;
}

int mul(ll a, int b){
	return (a * b) % MOD;
}

void sadd(int &a, int b){
	a = add(a, b);
}

void smul(int &a, int b){
	a = mul(a, b);
}

vector<int> divs[N];

int cnt[N];

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	string x;
	cin >> n >> x;
	n *= 2;
	string t = x;
	for(auto &c : t)
		c = (c == '0' ? '1' : '0');
	x.insert(x.end(), t.begin(), t.end());
	for(int i=1 ; i<=n ; i++)
		for(int j=i ; j<=n ; j+=i)
			divs[j].push_back(i);
	vector<int> ds;
	for(int i=1 ; i<=n ; i++)
		if(n%i == 0 && n%(2*i) != 0)
			ds.push_back(i);

	int ans=0;
	for(auto g : ds){
		int cur=0;
		string cx;
		for(int i=0 ; i<g/2 ; i++){
			smul(cur, 2);
			if(x[i] == '1')
				sadd(cur, 1);
			cx.push_back(x[i]);
		}
		sadd(cnt[g], cur);
		for(int i=0 ; i<g/2 ; i++)
			cx.push_back((cx[i] == '0' ? '1' : '0'));
		for(int i=g ; i<n ; i++)
			cx.push_back(cx[i%g]);
		if(cx <= x)
			sadd(cnt[g], 1);
		for(auto d : divs[g])
			if(d != g)
				sadd(cnt[g], -cnt[d]);
		sadd(ans, mul(g, cnt[g]));
	}
	cout << ans << "\n";
}














