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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=998244353;
int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector<int> vd;
	for(int i=1; i<=n; i+=2){
		if(n%i==0) vd.push_back(i);
	}
	ll ans=0;
	vector<ll> vc(vd.size());
	for(int i=0; i<vd.size(); i++){
		ll d=n/vd[i];
		ll cnt=0;
		for(int j=0; j<d; j++){
			cnt*=2;
			if(s[j]=='1') cnt++;
			cnt%=MOD;
		}
		string t=s.substr(0, d);
		for(int j=0; j<d; j+=2){
			if(t[j]=='0') t[j]='1';
			else t[j]='0';
		}
		string s2;
		for(int j=0; j<n/d; j++) s2+=t;
		for(int j=0; j<n; j++){
			int l=j/d;
			if((l+(j-l*d))%2==0){
				if(s2[j]=='0') s2[j]='1';
				else s2[j]='0';
			}
		}
		if(s2<=s) cnt++;
		vc[i]=cnt%MOD;
	}
	for(int i=(int)vd.size()-1; i>=0; i--){
		for(int j=i+1; j<vd.size(); j++){
			if(vd[j]%vd[i]==0) (vc[i]+=MOD-vc[j]);
		}
		vc[i]%=MOD;
		(ans+=vc[i]*(2*n/vd[i]))%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}