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;
#define sz(x) ((int) (x).size())

typedef long long ll;
const ll MOD = 998244353;
const int n = 2e5 + 10;

int N;
string X;
vector<int> D;
bool dPos[100];
bool S[n];
ll pw[n], C[n];
ll tmp[n];

int main(){
  cin >> N;
  cin >> X;
  for(int i=0; i<N; i++){
    S[i] = X[i] == '1';
  }
  pw[0] = 1;
  for(int i=1; i<=N; i++){
    pw[i] = pw[i-1] * 2;
    pw[i] %= MOD;
  }
  ll res = 0;
  for(int i=N; i>0; i--){
    if(N%i == 0 && N/i%2 == 1){
      D.push_back(i);
      dPos[sz(D)-1] = true;
    }
  }
  for(int x : D){
    C[x] = 2*x - tmp[x];
    for(int y : D){
      if(x%y == 0 && x != y){
        tmp[y] += C[x];
      }
    }
  }
  /*
  for(int x : D){
    cout << x << ": " << C[x] << endl;
  }
  */
  for(int i=0; i<N; i++){
    if(S[i]){
      for(int j=0; j<sz(D); j++){
        if(!dPos[j] || (D[j] <= i && !S[i-D[j]]))
          continue;
        int rem = max(0, D[j]-i-1);
        //cout << "rem " << D[j] << ": " << rem << " -> " << pw[rem] << " " << C[D[j]] << endl;
        res += pw[rem] * C[D[j]];
        res %= MOD;
      }
    }
    for(int j=0; j<sz(D); j++){
      if(i >= D[j]){
        dPos[j] &= S[i] != S[i-D[j]];
      }
    }
  }
  for(int j=0; j<sz(D); j++){
    if(dPos[j]){
      res += C[D[j]];
      res %= MOD;
    }
  }

  cout << res << endl;

  return 0;
}
