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;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans = 0;
const ll mo = 998244353;

int main()
{
auto mod = [](ll modx){modx%=mo;modx+=mo;modx%=mo;return modx;};
ll n ;
cin >> n ;
string x;
cin >> x;
ll oth=0;
vector<ll> ii;
ll tt=1;
rep(i,n){
  ii.push_back(tt);
  tt*=2;
  tt%=mo;
}
map<ll,ll> m;
for (ll i = n%2 ? n:n-1; i >= 3; i-=2)
{
  if(n%i==0 ){
    ll cou=1;
    ll tem=0;
    rep(j,(n/i)){
      if(x[j]=='1'){tem*=2;tem++;tem%=mo;}
      else {tem*=2;tem%=mo;}
    }
    tem++;
    while(1){
      bool ng=0;
      rep(j,(n/i)){
        if(cou%2&&x[j]=='1'&&x[j+cou*(n/i)]=='1'){
          ng=1;
          break;
        }
        else if(cou%2&&x[j]=='0'&&x[j+cou*(n/i)]=='0'){
          ng=1;
          tem--;
          break;
        }
        else if(cou%2==0&&x[j]=='1'&&x[j+cou*(n/i)]=='0'){
          ng=1;
          tem--;
          break;
        }
        else if(cou%2==0&&x[j]=='0'&&x[j+cou*(n/i)]=='1'){
          ng=1;
          break;
        }
      }
      if(ng)break;
      cou++;
      if(cou>=i)break;
    }
    if(tem<0)tem=0;
    for (auto j = m.begin(); j != m.end(); ++j) {
      if((n/i)%j->first==0 && ((n/i)/j->first)%2)tem-=j->second;
    }
    m[(n/i)]=tem;
    oth+=tem;
    oth%=mo;
    ans+=tem*(n/i)*2;
    ans%=mo;
    //cout << tem*(n/i)*2 <<" " << tem << endl;

  }
}

ll num=0;
rep(i,n){
  if(x[i]=='1')num+=ii[n-1-i];
  num%=mo;
}
ans+=mod(num-oth+1)*x.size()*2;

cout << ans%mo << endl;
return 0;
}
