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 <map>
#include <set>
#include <iostream> 
#include <queue>
#include <memory.h>
#include <math.h>
#include <vector>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;

const int mod = 998244353;
#define N 200002
#define ll long long

int mul(int x, int y) {
	return (ll)x*y%mod;
}

int add(int x, int y) {
	int ret = (x + y);
	if (ret < 0) {
		ret += mod;
	}
	if (ret >= mod) {
		ret -= mod;
	}
	return ret;
}
int res[N];
void solve() {
	int n;
	string s;
	cin >> n >> s;
	int g = n; while (g % 2 == 0)g /= 2;
	int v = n / g;
	int pos = 0;
	int ar[N];
	for (int i = 1; i <= g; ++i) {
		if (g%i == 0) {
			ar[pos++] = i;
		}
	}
	int cc = 0;
	for (int i = 0; i < n; ++i) {
		cc = mul(cc, 2);
		cc = add(cc, s[i] - '0');
	}
	cc = add(cc, 1);
	int ret = 0;
	for (int i = 0; i < pos; ++i) {
		int size = n/ar[i];
		int bucket = ar[i];
		int tmp = 0;
		string tt[2];
		for (int j = 0; j < size; ++j) {
			tmp = mul(tmp, 2);
			tmp = add(tmp, s[j] - '0');
			tt[0] += s[j];
			if (s[j] == '0') {
				tt[1] += '1';
			}
			else {
				tt[1] += '0';
			}
		}
		string k;
		for (int x = 0; x < bucket; ++x) {
			k += tt[ (x &1)];
		}
		if (s >= k) {
			tmp = add(tmp, 1);
		}
		res[bucket] = tmp;
	}
	for (int i = g; i >= 1; --i) {
		if (g%i == 0 && res[i] > 0) {
			for (int j = i + i + i; j <= g; j += i) {
				if (g%j==0) {
					res[i] = add(res[i], -res[j]);
				}
			}
			int u = (n * 2) / i;
			ret = add(ret, mul(u, res[i]));
		}
	}
	printf("%d\n", ret);
}
int main() {
	//freopen("input.txt", "r", stdin);
	solve();
}