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 INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

char s[200010];
int n;
int ans;
int val[200010]; // val[i]表示以 i为循环节长度的方案数
vector<int>divs; // 所有 2n/2divs[idx] 为奇数


// 以 s[0..len-1]为 循环节 [正][取反][正]这样产生的长n的字符串的 方案数
ll cnt(int len) {
  int ans = 0;
  rep(i,0,len){
    ((ans*=2)+=s[i]-'0')%=MOD;
  }
  // [0.........................n]
  // [0...len][反0...len][0...len]
  // s>=t ans+1
  // t>s ans+1
  // 因为统计了全零所以+1, 如果t比s大那么[0..len]作为循环节不行,把 [0..len] 值减1可行 所以 全零+1,再-1就是ans
  rep(i,0,n){
    char ti = ((s[i%len]-'0')^((i/len)%2))+'0';
    if (s[i] > ti) return ans + 1;
    if (ti > s[i]) return ans;
  }
  return ans + 1;
}

int main() {
  cin>>n;
  scanf("%s", s);
  rep(i,1,n+1){
    if (n % i == 0 && (n / i) % 2 == 1){
      divs.pb(i);
    }
  }
  ll ans = cnt(n) * (2 * n) % MOD; // 全部都是2n 次
  per(idx,0,divs.size()){
    int i = divs[idx];
    val[i] = (2*i-2*n) % MOD;
    rep(j,idx+1,divs.size()){
      if(divs[j] % divs[idx] == 0){
        (val[i]-=val[divs[j]])%=MOD;
      }
    }
    (ans += cnt(i) * val[i] )%=MOD;
  }
  cout<<(ans+MOD)%MOD<<endl;
  return 0;
}
