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 pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y>a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[200613];
int l[200610];
long long j[3020];

long long x,y,z[200101],mod=998244353;
string r;
//char r[111];

P u[1];
queue<int> q;

stack<int> s;
map<int,int> p;
vector<int> v;

bool as(P a,P b)
{
  if(a.x==b.x)
  return a.y<b.y;
  return a.x<b.x;
}

int main()
{
  scanf("%d",&a);
  z[0]=1;
  for(int t=1;t<=a;t++)
    z[t]=z[t-1]*2%mod;
  for(int t=0;t<a;t++)
    scanf("%1d",&o[t]);
  for(int t=1;t<=a;t+=2)
  if(a%t==0) v.push_back(a/t);
  reverse(v.begin(),v.end());
  for(int t=0;t<v.size();t++)
  {
    int k=0;
    for(int i=0;i<a;i++)
      if(i/v[t]%2==0)l[i]=o[i%(v[t])];
      else l[i]=1-o[i%(v[t])];
    //printf("%d ",v[t]);
    //for(int i=0;i<a;i++)
    //printf("%d",l[i]);
    for(int i=0;i<a;i++)
    {
      if(o[i]>l[i]) break;
      if(o[i]<l[i])
      {
        k=1;
        break;
      }
    }
    //puts("");
    //for(int i=0;i<a;i++)
   // printf("%d",l[i]);
    //puts("");
    x=1;
    for(int i=v[t]-1;i>=0;i--)
      if(l[i]==1) x+=z[v[t]-1-i],x%=mod;
    j[t]=x-k;
    for(int h=0;h<t;h++)
    if(v[t]%v[h]==0) j[t]=(j[t]-j[h]+mod)%mod;
    y+=j[t]*2%mod*v[t]%mod;
    y%=mod;
    //printf("%d\n",j[t]);
  }
  printf("%lld",y);
}



