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;

typedef long long LL;

const int N=200000,mod=998244353;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int n;
char s[N+9];

void into(){
  scanf("%d%s",&n,s+1);
}

int pw[N+9];

void Get_pw(){
  pw[0]=1;
  for (int i=1;i<=n;++i) pw[i]=mul(pw[i-1],2);
}

int ans0,ans[N+9];

bool Check_ans(int p){
  for (int i=0,opt=0;i<n;i+=p,opt^=1)
	for (int j=1;j<=p;++j)
	  if (s[j]^opt^s[i+j]) return (s[j]^opt)<s[i+j];
  return 1;
}

void Get_ans(){
  for (int i=1;i<=n;++i){
	if (n%i||n/i&1^1) continue;
	for (int j=1;j<=i;++j)
	  if (s[j]=='1') sadd(ans[i],pw[i-j]);
    if (Check_ans(i)) sadd(ans[i],1);
  }
  for (int i=1;i<=n;++i){
	if (n%i||n/i&1^1) continue;
	for (int j=2;i*j<=n;++j) ssub(ans[i*j],ans[i]);
	sadd(ans0,mul(ans[i],i));
  }
}

void work(){
  Get_pw();
  Get_ans();
}

void outo(){
  printf("%d\n",mul(ans0,2));
}

int main(){
  into();
  work();
  outo();
  return 0;
}