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 MAX 200010
#define MOD 998244353
using namespace std;

int N;
int powerTwo[MAX];
char str[MAX];
char number[MAX];
char example[MAX * 2];
int weight[MAX];

int rotate(int i)
{
	int two = !(i & 1);
	i >>= 1;
	i |= (two << (N - 1));
	return i;
}

int add(int a, int b)
{
	return (a + b) % MOD;
}

int sub(int a, int b)
{
	return (a + MOD - b) % MOD;
}

int prod(int a, int b)
{
	return 1LL * a * b % MOD;
}

int main(void)
{
	cin >> N;
	cin >> str;
	powerTwo[0] = 1;
	for (int i = 1; i < N; i++) powerTwo[i] = add(powerTwo[i - 1], powerTwo[i - 1]);
	int K = strlen(str);
	for (int i = 0; i < N - K; i++) number[i] = '0';
	for (int i = N - K; i < N; i++) number[i] = str[i - (N - K)];
	K = 0;
	for (int i = 0; i < N; i++)
	{
		if (number[i] == '1') K = add(K, powerTwo[N - 1 - i]);
		weight[i] = 2 * N;
	}
	weight[N] = 2 * N;
	int ans = prod(2 * N, K + 1);
	for (int i = 3; i <= N; i += 2)
	{
		if (N % i) continue;
		int coeff = 0;
		for (int j = 0; j < N / i; j++)
		{
			if (number[j] == '1') coeff = add(coeff, powerTwo[N / i - 1 - j]);
		}
		weight[i] = sub(weight[i], 2 * N / i);
		ans = sub(ans, prod(coeff, weight[i]));
		for (int j = 0; j < N / i; j++) example[j] = number[j];
		for (int j = N / i; j < N; j++) example[j] = '0' + (example[j - N / i] == '0');
		if (strcmp(example, number) <= 0) ans = sub(ans, weight[i]);
		for (int j = i * 2; j <= N; j += i) weight[j] = sub(weight[j], weight[i]);
	}
	cout << ans << endl;
	return 0;
}
