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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
ll mod=998244353;
ll n;

string bit(ll nn,ll nx){
  string ans="";
  for(int i=0;i<nx;i++){
    char c=nn%2+'0';
    ans=c+ans;
    nn/=2;
  }
  return ans;
}

int main(){
  string x;
  cin >> n >> x;
  ll sum=0,c=1;
  for(int i=n-1;i>=0;i--){
    if(x[i]=='1'){
      sum+=c; sum%=mod;
    }
    c*=2; c%=mod;
  }
  ll ans=(sum+1)*2*n%mod;
  vector<ll> cnt(n);
  for(int i=n/2*2+1;i>=3;i-=2){
    if(n%i==0){
      ll y=1,z=0;
      int k=n/i;
      for(int j=k-1;j>=0;j--){
        if(x[j]=='1'){
          z+=y; z%=mod;
        }
        y*=2; y%=mod;
      }
      cnt[k]+=z;
      string st="";
      string sts=x.substr(0,k);
      string stt="";
      for(int j=0;j<k;j++){
        if(sts[j]=='0') stt+='1';
        else stt+='0';
      }
      for(int j=0;j<i;j++){
        if(j%2==0) st+=sts;
        else st+=stt;
      }
      cerr << st << endl;
      if(st<=x) cnt[k]++;
      for(int j=1;j<k;j++){
        if(k%j==0) cnt[k]-=cnt[j];
      }
      ans=(ans+mod-(2*(n-k)*cnt[k])%mod)%mod;
    }
  }
  cout << ans << endl;
}