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 <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

ll ans = 0, n = 0;
ll P = 998244353;
string x;
std::vector<ll> rui(300000, 1);
std::vector<ll> minu(300000, 0);

void check(ll num, ll block){
  ll o = 0;
  for(int i=0;i<num;i++) if(x[i]=='1') o = (o+rui[num-1-i])%P;
  string s="";
  for(int i=0;i<block;i++) for(int j=0;j<num;j++) s+=(i%2==0?x[j]:(x[j]=='1'?'0':'1'));
  if(s<=x) o = (o+1)%P;
  //std::cout << num << " " << o << '\n';
  ll tmp = (o-minu[num]); //current number
  for(int i=2;i*num<300000;i++) minu[i*num] = (minu[i*num] + tmp)%P;
  ans = (ans - ((2*(n-num)*tmp)%P) + P)%P;
}
int main(int argc, char const *argv[]) {
  std::cin >> n;std::cin >> x;
  ans = 2*n;
  for(int i=0;i<n;i++) {
    rui[i] = (i==0?1:(rui[i-1]*2)%P);
    if(x[n-1-i]=='1') ans = (ans + ((rui[i]*2*n)%P))%P;
  }
  vvl q = vv(0, 2, 0, ll);
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      if(i*i==n&&i%2==1) q.push_back(vll{i, i});
      if(i*i!=n){
        if(i%2==1) q.push_back(vll{n/i, i});
        if((n/i)%2==1) q.push_back(vll{i, n/i});
      }
    }
  }
  sort(q.begin(), q.end());
  for(int i=0;i<q.size();i++) check(q[i][0], q[i][1]);
  std::cout << ans << '\n';
  return 0;
}
