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>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
typedef long long ll;
using namespace std;

int N;
string X;
ll t[200000], a[200001], p, res;

int main() {
	cin >> N >> X;
	t[0] = (X[0] == '1');
	for (int i = 1; i < N; ++i) {
		t[i] = (t[i - 1] * 2 + (X[i] == '1')) % mod998;
	}
	for (int i = 2; i <= N; i += 2) {
		if (N % i == i / 2) {
			bool f = true;
			bool g = false;
			for (int j = 0; j < i / 2; ++j) {
				if (X[j] == '0') {
					if (X[j + i / 2] == '0') {
						f = false;
						break;
					}
				}
				else {
					if (X[j + i / 2] == '1') {
						g = true;
						break;
					}
				}
			}
			if (f&&!g) {
				string T;
				for (int j = 0; j < i; ++j) {
					T.push_back(X[j]);
				}
				for (int j = 0; j < i; ++j) {
					if (X[j] == '0') {
						T.push_back('1');
					}
					else {
						T.push_back('0');
					}
				}
				for (int j = 0; j < N; ++j) {
					if (T[j%i] == '0'&&X[j] == '1') {
						break;
					}
					if (T[j%i] == '1'&&X[j] == '0') {
						f = false;
						break;
					}
				}
			}
			if(f) {
				a[i] = t[i / 2 - 1] + 1;
			}
			else {
				a[i] = t[i / 2 - 1];
			}
		}
	}
	p = t[N - 1] + 1;
	for (int i = 2; i <= N; ++i) {
		if (a[i]) {
			res += a[i] * i;
			res %= mod998;
			for (int j = i + i; j <= N; j += i) {
				if (a[j]) {
					a[j] -= a[i];
					a[j] += mod998;
					a[j] %= mod998;
				}
			}
			p -= a[i];
			p += mod998;
			p %= mod998;
		}
	}
	res += p * 2 * N;
	res %= mod998;
	cout << res << endl;
}