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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, w[202000], chk[2020], sz;
char p[202000];
long long D[202000], po[202000], Mod = 998244353;
vector<int>T;
int main() {
	int i, j, k;
	scanf("%d", &n);
	po[0] = 1;
	for (i = 1; i <= n; i++)po[i] = po[i - 1] * 2 % Mod;
	scanf("%s", p);
	for (i = 0; i < n; i++) {
		w[n - i - 1] = p[i] - '0';
	}
	for (i = 1; i <= n; i+=2) {
		if (n%i == 0) {
			T.push_back(i);
		}
	}
	sz = T.size();
	for (i = n - 1; i >= 0; i--) {
		if (w[i] == 1) {
			for (j = 0; j < sz; j++) {
				if (chk[j])continue;
				int l = n / T[j];
				if (n - 1 >= i + l && w[i + l] == 0)continue;
				long long t = 1;
				if (n - i < l) t = po[l-(n-i)];
				D[j] = (D[j] + t) % Mod;
			}
		}
		for (j = 0; j < sz; j++) {
			int l = n / T[j];
			if (n - 1 >= i + l && w[i + l] == w[i]) chk[j] = 1;
		}
	}
	for (j = 0; j < sz; j++) {
		if (chk[j])continue;
		long long t = 1;
		D[j] = (D[j] + t) % Mod;
	}
	long long res = 0;
	for (j = sz - 1; j >= 0; j--) {
		for (k = sz - 1; k > j; k--) {
			if (T[k] % T[j] == 0) {
				D[j] = (D[j] - D[k] + Mod) % Mod;
			}
		}
		res = (res + (n / T[j]) * 2 * D[j]) % Mod;
	}
	printf("%lld\n", res);
}