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;

const int P = 998244353;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	string s;
	cin >> s;

	vector<vector<long long> > dp(n + 1, vector<long long> (2));
	dp[0][1] = 1;

	vector<long long> f(n);
	vector<bool> vis(n);

	long long cnt = 0;

	for(int i = 0; i < n; ++i) {
		dp[i + 1][0] = dp[i][0] * 2 % P;
		dp[i + 1][1] = dp[i][1];
		if(s[i] == '1') {
			dp[i + 1][0] = (dp[i + 1][0] + dp[i][1]) % P;
		}
	}

	for(int i = 0; i + i + i + 3 <= n; ++i) {
		if((n * 2) % (2 * i + 2) == 0 && ((n * 2) / (2 * i + 2)) % 2 == 1) {
			string tmp = "";
			string t = "";
			for(int j = 0; j <= i; ++j) {
				tmp += s[j];
			}
			for(int j = 0; j <= i; ++j) {
				if(s[j] == '0') {
					tmp += '1';
				} else {
					tmp += '0';
				}
			}
			for(int j = 0; j < n; ++j) {
				t += tmp[j % (i * 2 + 2)];
			}
			long long x = dp[i + 1][0] + (t <= s);
			f[i] = x % P;
			vis[i] = true;
		} 
	}

	for(int i = 1; i <= n; ++i) {
		if(vis[i - 1]) {
			for(int j = i + i; j <= n; j += i) {
				if(vis[j - 1]) {
					f[j - 1] = (f[j - 1] - f[i - 1] + P) % P;
				}
			}
		}
	}

	long long ans = 0;
	long long tot = (dp[n][0] + dp[n][1]) % P;
	for(int i = 0; i < n; ++i) {
		if(vis[i]) {
			tot = (tot - f[i] + P) % P;
		}
	}
	ans = (ans + tot * n * 2) % P;
	for(int i = 0; i < n; ++i) {
		if(vis[i]) {
			ans = (ans + f[i] * (i + 1) * 2) % P;
		}
	}

	cout << ans << '\n';

	return 0;
}
