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>
using namespace std;

#define F first
#define S second
#define PB push_back
#define all(x) x.begin(), x.end()

typedef long long ll; 
typedef long double ld;
typedef pair<ll, ll> pll;

const int N = 1000 * 1000 + 10; 
int mod = 998244353;

ll ans[N];

int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n;
	string s;
	cin>> n >> s;
	ll Ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(n % i != 0 || n % (i * 2) == 0) continue;
		ans[i] = (mod + ans[i]) % mod;
		int res = 0;
		string t = "", ttt = "";
		for(int j = 0; j < i; j++) 
		{
			res = res * 2 + s[j] - '0';
			res %= mod;
			t += s[j];
			ttt += s[j] == '0' ? '1' : '0';
		}
		ans[i] += res;
		ans[i] %= mod;
		
		string all = "";
		for(int j = 0; j < n / i; j++) all += (j % 2 == 0 ? t : ttt);
		
		if(all <= s) ans[i]++;
		Ans += 2ll * ans[i] * i % mod; Ans %= mod;
		for(int j = 3 * i; j <= n; j += 2 * i) ans[j] -= ans[i], ans[j] %= mod;
	}
	cout<< Ans << endl;
}