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;
int powow(long long p){
  long long r = 1;
  long long w = 2;
  while(p > 0){
  if(p & 1)r = r * w % 998244353;
  w = w * w % 998244353;
  p >>= 1;}
  return r;
}

int main() {
  int b;
  cin >> b;
  string aa;
  cin >> aa;
  vector<int> a(b);
  vector<long long> kaburi(b);
  long long f=0;
  for(int i = 0;i < b;i++){
    if(aa.at(i) == '1')a.at(i) = 1;
    if(a.at(i) == 1){f += powow(b-i-1);}
  }
  f++;
  f %= 998244353;
  f *= b*2;
  f %= 998244353;
  long long iran = 0;
  for(int i = 1;i < b;i++){
    long long t = 0;
    if(b % (2*i) != 0 && b % i == 0){
      for(int j = 0;j < i;j++){
        if(a.at(j)){t += powow(i-j-1);}
      }
    
      vector<int> hhh(b);
      vector<int> ggg(b);
      for(int j = 0;j < b;j++){
        hhh.at(j) = a.at(j%i);
        ggg.at(j) = a.at(j);
        if(j % (2*i) >= i)hhh.at(j) = hhh.at(j) * -1 +1;

          }

      if(ggg >= hhh){t++;}
        t %= 998244353;
      
      
      for(int j = 1;j < i;j++){
        if(i%j==0){
        t=(t-kaburi.at(j)+998244353)%998244353;}
      }
        kaburi.at(i) = t;
        t *= (b-i)*2;
        t %= 998244353;
     
        iran += t;}
   
    }

  iran = iran % 998244353;
  f = f - iran + 998244353;
  f %= 998244353;
  cout << f << endl;
       
  }