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
//Solution by Tima
#include <bits/stdc++.h>
 
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
 
using namespace std;    
const int N = int(3e5) + 12, mod = 998244353; 

int n;
string s,t,p,q;

ll cnt[N];
vector <int> dv;

int main () {
	cin >> n >> s;
	int d = 1;
	int m = n;
	while(m % 2 == 0){
		d = d * 2;
		m /= 2;
	}
	ll ans = 0;
	for(int j = d; j <= n; j += d) if(n % j == 0){
		ll res = 0;
		p = "", q = "";;
		t = "";
		for(int i = 0; i < j; i++){
			res = (res * 2 + s[i] - '0') % mod;
			p += s[i];
			q += char(1 - (s[i] - '0') + '0');
		}
		int cur = 1;
		while(t.size() < s.size()) {
			if(cur) t += p;
			else t += q;
			cur ^= 1;
		}
		if(t <= s) res++;
		cnt[j] = res;
		for(int v : dv) if(j % v == 0) {
			cnt[j] -= cnt[v];
			if(cnt[j] < 0) cnt[j] += mod;
		}
		dv.pb(j);
		ans = (ans + 1ll * cnt[j] * j * 2) % mod;
	}
	cout << (ans + mod) % mod;
 
return 0;
}