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 MOD = 998244353;
const int MAXN = 200005;

int N, p2[MAXN], sub[MAXN];
char x[MAXN];

int main(){
	scanf("%d %s", &N, x);
	for(int i = 0; i < N; i++){
		if(i == 0)p2[i] = 1;
		else p2[i] = 2LL * p2[i - 1] % MOD;
	}
	
	long long res = 0;
	for(int d = N; d >= 1; d--){
		if(d % 2 == 0)continue;
		if(N % d != 0)continue;
		
		int l = N / d;
		
		long long r = 0;
		for(int i = 0; i < l; i++)
			if(x[i] == '1')r = (r + p2[l - i - 1]) % MOD;
	
		bool ok = true;
		for(int i = 0; i < N; i++){
			char y = x[i % l];
			if(i % (2 * l) >= l)y ^= '0' ^ '1';
			
			if(x[i] > y)break;
			else if(x[i] < y){
				ok = false;
				break;
			}
		}
		if(ok)r = (r + 1) % MOD;
		r = (r - sub[d] + MOD) % MOD;
		
		res = (res + 2LL * r * l) % MOD;
		
		for(int d2 = 1; d2 < d; d2++)
			if(d % d2 == 0)sub[d2] = (sub[d2] + r) % MOD;
	}
	printf("%lld\n", res);
	
	return 0;
}
