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 <iostream>
#include <cstdio>
#define MN 201000
#define mod 998244353

int n; 
int s[MN], mi[MN];
int g[MN], f[MN];
int lst[MN];

void check(int x)
{
	for(int i = 0; i < n; i++)
	{
		if(s[i] == 1)
		{
			if(i < x || lst[i % x] == 1)
			{
				if(i < x) g[x] = (g[x] + mi[x - i - 1]) % mod;
				else g[x] = (g[x] + 1) % mod;
			}
		}
		if(i == n - 1)
		{
			if(i < x || s[i] != lst[i % x]) g[x] = (g[x] + 1) % mod;
			continue;
		}
		if(i >= x)
		{
			if(s[i] == lst[i % x]) return;
		}
		lst[i % x] = s[i];
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%1d", &s[i]);
	mi[0] = 1; for(int i = 1; i <= n; i++) mi[i] = mi[i - 1] * 2 % mod;
	for(int i = 1; i * i <= n; i++)
	{
		if(n % i == 0)
		{
			if(n / i % 2 == 1) check(i);
			if(i != n / i && (i & 1)) check(n / i); 
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(n % i == 0 && n / i % 2 == 1)
		{
			f[i] = g[i];
			for(int j = 1; j * j <= i; j++)
			{
				if(i % j == 0)
				{
					if(j != i) f[i] = (f[i] - f[j] + mod) % mod;
					if(i / j != j && i / j != i) f[i] = (f[i] - f[i / j] + mod) % mod;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ans = (ans + 1ll * i * 2 * f[i]) % mod;
	}
	printf("%d\n", ans);
}