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 ll long long
using namespace std;
const int N = 200010, Mod = 998244353;
int f[N]; char st[N];
int main() {
	ios::sync_with_stdio(false);
	int n; cin >> n >> st;
	for (int i = 1; i <= n; i += 2) {
		if (n % i != 0) continue;
		int m = n / i, fl = 1;
		for (int j = 0; j < m; j++) f[i] = (2ll * f[i] % Mod + st[j] - '0') % Mod;
		for (int j = m; j < n; j++)
			if (st[j] != (st[j % m] ^ (j / m & 1))) {fl = st[j] > (st[j % m] ^ (j / m & 1)); break;}
		(f[i] += fl) %= Mod;
	}
	int ans = 0;
	for (int i = n; i; i--) {
		for (int j = i + i; j <= n; j += i)
			(f[i] += Mod - f[j]) %= Mod;
		(ans += 2ll * f[i] % Mod * (n / i) % Mod) %= Mod;
	}
	cout << ans << '\n';
	return 0;
}