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 MAXN = 202020;
const int P = 998244353;
char s[MAXN], t[MAXN];
bool vis[MAXN];
int n, ans, val[MAXN];
void update(int &x, int y)
{
	x += y;
	if (x >= P)
		x -= P;
}
int cnt(int x)
{
	int ans = 0;
	for (int i = 1; i <= x; i++)
		ans = ((ans * 2) + (s[i] - '0')) % P;
	int tmp = 1;
	for (int i = 1; i <= n; i++)
	{
		if(tmp <= x)
			t[i] = s[tmp];
		else
			t[i] = s[tmp - x] ^ 1;
		tmp = (tmp == 2 * x) ? 1 : (tmp + 1);
	}	
	for (int i = 1; i <= n; i++)
	{
		if (s[i] > t[i])
			return ans + 1;
		if (t[i] > s[i])
			return ans;
	}
	return ans + 1;
}
int main()
{
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++)
		if (n % i == 0 && (n / i) % 2 == 1)
			vis[i] = true;
	int ans = 1ll * cnt(n) * (2 * n) % P;
	for(int i = n - 1; i >= 1; i--)
	{
		if(!vis[i])
			continue;
		int tmp = 2 * n;
		for(int j = i; j <= n; j += i)
			if(vis[j])
				update(tmp, val[j]);
		val[i] = 2 * i;
		update(val[i], P - tmp);
		update(ans, 1ll * cnt(i) * val[i] % P);
	}
	printf("%d\n", ans);
	return 0;
}