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;
#define ll long long
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 400000, md = 998244353;
int dp[N + 1], n, n2, p2[N + 1];
bool ok[N + 1];
char s[N], z[N];

void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
void sb(int &x, int y) { if ((x -= y) <  0 )x += md; }

bool fl(int x){
	f(i, x, n)z[i] = z[i - x] ^ 1;
	f(i, 0, n)if (z[i] < s[i])return true;
	else if (z[i] > s[i])return false;
	return true;
}

void go(int x){
	x >>= 1;
	f(i, 0, x){
		if (s[i] == '1')ad(dp[x << 1], p2[x - i - 1]);
		z[i] = s[i];
	}
	if (fl(x))ad(dp[x << 1], 1);
}

int main(){
	scanf("%d%s", &n, s);
	n2 = n << 1;
	p2[0] = 1;
	f(i, 1, n2 + 1)ad(p2[i] = p2[i - 1], p2[i - 1]);
	f(i, 1, n2 + 1)if (n % i && n2 % i == 0)ok[i] = true;
	f(i, 1, n2 + 1)if (ok[i])go(i);
	f(i, 1, n2 + 1)if (ok[i])for (int j = i << 1; j <= n2; j += i)sb(dp[j], dp[i]);
	int an = 0;
	f(i, 1, n2 + 1)if (ok[i])ad(an, (ll)i * dp[i] % md);
	printf("%d\n", an);
}