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>
#define ll long long

using namespace std;

const ll mod = 998244353; 
const int N = 500200; 

int n; 
int a[N], t[N]; 
int mx[N], mn[N]; 
ll F[N]; 

int main() {


  scanf("%d", &n); 
  for (int i = 1; i <= n; i++)
    scanf("%1d", &a[i]);
  for (int i = 1; i <= (n << 1); i++) {
    if ((n << 1) % i != 0 || !(((n << 1) / i) & 1)) 
      continue ; 
    for (int j = 1; j <= (n / (i / 2)); j++) 
      for (int k = 1; k <= i / 2; k++) {
        t[(j - 1) * (i / 2) + k] = (j % 2 == 1) ? a[k] : a[k] ^ 1;
    }
    ll C = 0; 
    for(int j = 1; j <= i / 2; j++) {
      C = (C * 2 % mod + t[j]) % mod; 
    }
    F[i] = C + (vector <int>(t + 1, t + n + 1) <= vector <int>(a + 1, a + n + 1)); 
  }
  ll ans = 0; 
  for (int i = 1; i <= 2 * n; i++) {
    if((2 * n % i == 0) && ((2 * n / i) & 1)) {
      ans = (ans + F[i] * i % mod) % mod; 
      for (int j = i + i; j <= 2 * n; j += i) {
        if((2 * n % j == 0) && ((2 * n / j) & 1))
          F[j] = (mod + (F[j] - F[i]) % mod) % mod; 
      }
    }
  }
  printf("%lld\n", ans); 
  return 0; 
}