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 mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN = 200005, mod = 998244353;
int n;
string a;
vector<LL> v;
LL ans = 0, cnt[MAXN];

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a;
    for(int i = 1; i <= n; ++i)
    	if(n % i == 0 && (n / i) % 2 == 1)
    		v.pb(i);
    for(int i = 0; i < v.size(); ++i) {
    	int x = v[i];
    	//cout << x << endl;
    	string s, t, s0;
    	LL val = 0;
    	for(int j = 0; j < x; ++j) {
    		val *= 2;
    		val += a[j] - '0';
    		val %= mod;
    		s += a[j];
    		s0 += '0' + '1' - a[j];
    	}
    	t = s;
    	while(t.size() < a.size())
    		t += s0 + s;
    	//cout << t << " " << s << endl;
    	cnt[i] = val;
    	if(t <= a)
    		++cnt[i];
    	cnt[i] %= mod;
    }
    for(int i = 0; i < v.size(); ++i)
    	for(int j = i + 1; j < v.size(); ++j)
    		if(v[j] % v[i] == 0) {
    			cnt[j] -= cnt[i];
    			if(cnt[j] < 0)
    				cnt[j] += mod;
    		}
    for(int i = 0; i < v.size(); ++i) {
    	//cout << v[i] << " " << cnt[i] << endl;
    	ans += cnt[i] * v[i] * 2;
    	ans %= mod;
    }
    cout << ans << endl;

}