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
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
//using namespace __gnu_pbds;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
//using oset = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 17*7*(1<<23) + 1;
ll n, f[400400];
string s;
ll get(ll k) {
	ll ans = 0;
	for(int i = 0; i < k; i++) {
		ans = ((ans<<1)+(s[i]=='1'))%mod;
	}
	int i = 0;
	while(i+k<s.size()&&s[i]!=s[i+k])i++;
	if(i+k>=s.size()||s[i+k]=='1')ans++;
	return ans%mod;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		if(n%i||(n/i)%2==0) continue;
		f[i] += get(i);
		for(int j = i+i; j <= 2*n; j+=i)
			f[j]-=f[i];
		ans = (ans + 2ll*i*f[i])%mod;
	}
	if(ans < 0)
		ans %= mod, ans += mod;
	cout << ans << "\n";
}
