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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)998244353;

int n;
string s;
vector<int> vec, vec2;
long long cnt[200009], ans;

bool fun(int len)
{
	for (int i = 0; i < n; i++) {
		char c = s[i%len];
		if ((i / len)%2) {
			if (c == '1') c = '0';
			else c = '1';
		}
		if (s[i] < c) return false;
		else if (s[i] > c) return true;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for (int i = 1; i <= n; i += 2) {
		if (n%i == 0) vec.pb(i);
	}
	for (int i = 0; i < (int)vec.size(); i++) {
		int cur = n/vec[i];
		vec2.pb(cur);
		long long un = 1;
		for (int j = cur - 1; j >= 0; j--) {
			if (s[j] == '1') {
				cnt[cur] += un;
				cnt[cur] %= MOD;
			}
			un *= 2;
			un %= MOD;
		}
		if (fun(cur)) {
			cnt[cur] ++;
			cnt[cur] %= MOD;
		}
	}
	sort(vec2.begin(), vec2.end());
	for (int i = 0; i < (int)vec2.size(); i++) {
		int ti = vec2[i];
		for (int j = i + 1; j < (int)vec2.size(); j++) {
			int tj = vec2[j];
			if (tj % ti == 0) {
				cnt[tj] = cnt[tj] - cnt[ti] + MOD;
				cnt[tj] %= MOD;
			}
		}
		ans += cnt[ti]*ti*2;
		ans %= MOD;
	}
	cout << ans << E;
	//system("pause");
	return 0;
}