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 vector<int> vi;
typedef long long ll;
const int MN = 200200;
const ll M = 998244353;
int st[MN];
bitset<MN> dv;
vi fac;
ll ct[MN];
inline ll mul(ll a, ll b) {return (a*b)%M;}
inline ll norm(ll n) {return ((n%M)+M)%M;}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i=0;i<n;i++) {
		st[i] = s[i]-'0';
	}
	for(int i=1;i<=n;i+=2) {
		if(!(n%i)) {
			dv.set(n/i);
			fac.push_back(i);
		}
	}
	for(int i=0;i<fac.size();i++) {
		ll val = 0;
		ll sz = n/fac[i];
		ll sub = 0;
		for(int i=0;i<sz;i++) {
			val *= 2;
			val += st[i];
			val %= M;
		}
		for(int i=sz;i<n;i++) {
			if(st[i] > 1-st[i-sz]) {
				break;
			}
			if(st[i] < 1-st[i-sz]) {
				sub = 1;break;
			}
		}
		val += 1-sub;
		val %= M;
		ct[sz] = val;
	}
	for(int i=1;i<=n;i++) {
		if(dv[i]) {
			for(int j=2;j*i<=n;j++) {
				if(dv[i*j]) {
					ct[i*j] -= ct[i];
					ct[i*j] = norm(ct[i*j]);
				}
			}
		}
	}
	ll res = 0;
	for(int i=0;i<=n;i++) {
		if(dv[i]) {
			res += norm(2*i*ct[i]);
		}
	}
	cout << norm(res) << '\n';
}
