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 f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)2e5 + 123, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int n, m, d[N];
ll a[N], dp[N], ans;
char s[N];
bool check(int x){
	for(int i = x; i < n; i++){
		int val = ('1' ^ '0' ^ s[i - x]);
		if(val == s[i])
			continue;
		if(val < s[i])
			return 1;
		if(val > s[i])
			return 0;
	}
	return 1;
}
int main()
{
	scanf("%d", &n);
	scanf("%s", &s);
	for(int i = 1; i <= n; i++){
		a[i] = a[i - 1] * 2 % mod;
		if(s[i - 1] == '1')
			a[i]++;
	}
	for(int i = 1; i <= n; i++)
		if((i & 1) && n % i == 0)
			d[m++] = n / i;	
	for(int i = 0; i < m; i++)
		dp[i] = (a[d[i]] + check(d[i]) + mod) % mod;		
    for(int i = m - 1; i >= 0; i--){
	    for(int j = 0; j < i; j++)
			if(d[j] % d[i] == 0)
				dp[j] = (dp[j] - dp[i] + mod) % mod;				 
	}                                  
	for(int i = 0; i < m; i++)
		ans = (ans + dp[i] * d[i]) % mod;
	cout << 2 * ans % mod;
	return 0;
}
