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 <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=2e5+5,Mo=998244353;

int n,pw[N],c[N],d[N],m;
char x[N];

bool chk(int l) {
	fo(i,l+1,n) {
		int c=(x[i-l]-'0')^1,a=x[i]-'0';
		if (c>a) return 0;
		if (c<a) return 1;
	}
	return 1;
}

void inc(int &x,int y) {x=x+y>=Mo?x+y-Mo:x+y;}
void dec(int &x,int y) {x=x-y<0?x-y+Mo:x-y;}

int main() {
	scanf("%d",&n);
	scanf("%s",x+1);
	pw[0]=0;fo(i,1,n) pw[i]=(pw[i-1]<<1|(x[i]-'0'))%Mo;
	fo(i,1,n-1) if (!(n%i)&&((n/i)&1)) d[++m]=i,c[m]=pw[i]+chk(i);
	fo(i,1,m) fo(j,1,i-1) if (!(d[i]%d[j])&&((d[i]/d[j])&1)) dec(c[i],c[j]);
	int cnt=pw[n]+1,ans=0;
	fo(i,1,m) dec(cnt,c[i]),inc(ans,(ll)(d[i]<<1)*c[i]%Mo);
	inc(ans,(ll)(n<<1)*cnt%Mo);
	printf("%d\n",ans);
	return 0;
}
