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>

typedef long long LL;

const int N=200005;
const int MOD=998244353;

int n,a[N],f[N];
char str[N];

int solve(int t)
{
	int s=0;
	for (int i=0;i<t;i++) s=(s*2+a[i])%MOD;
	bool flag=0;
	for (int i=t;i<n;i++)
		if (a[i]<(a[i%t]^((i/t)&1))) {flag=1;break;}
		else if (a[i]>(a[i%t]^((i/t)&1))) break;
	if (!flag) s++;
	return s;
}

int main()
{
	scanf("%d",&n);
	scanf("%s",str);
	int r=0;
	for (int i=0;i<n;i++) a[i]=str[i]-'0',r=(r*2+a[i])%MOD;;
	r++;
	for (int i=1;i<=n;i++)
		if (n%i==0&&n/i%2==1)
		{
			(f[i]+=solve(i))%=MOD;
			for (int j=i*2;j<=n;j+=i)
				if (n%j==0) (f[j]+=MOD-f[i])%=MOD;
			(r+=MOD-f[i])%=MOD;
		}
	int ans=(LL)r*n*2%MOD;
	for (int i=1;i<=n;i++)
		if (n%i==0&&n/i%2==1) (ans+=(LL)f[i]*i*2%MOD)%=MOD;
	printf("%d\n",ans);
	return 0;
}
