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;

const int mod = 998244353;

int add(int a, int b) {
  return a + b - mod * (a + b >= mod);
}

int mul(int a, int b) {
  return int(1ll * a * b % mod);
}

int power(int a, int x) {
  if (x == 0) {
    return 1;
  }
  return mul(power(mul(a, a), x >> 1), (x & 1 ? a : 1));
}

int divide(int a, int b) {
  return mul(a, power(b, mod - 2));
}

int sub(int a, int b) {
  return a - b + mod * (a < b);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int n;
  string s;
  cin >> n >> s;
  vector<int> ans(n + 1);
  for (int i = 1; i <= n; ++i) {
    if (n % i or (i & 1) == 0) {
      continue;
    }
    int k = n / i, res = 0;
    for (int j = 0; j < k; ++j) {
      res = add(res, res);
      if (s[j] == '1') {
        res = add(res, 1);
      }
    }
    for (int j = 0; j <= n; ++j) {
      if (j == n) {
        res = add(res, 1);
        break;
      }
      char c1 = s[j], c2;
      int p = j % (2 * k);
      if (p < k) {
        c2 = s[p];
      } else {
        c2 = '0' + '1' - s[p - k];
      }
      if (c1 == c2) {
        continue;
      } else if (c1 < c2) {
        break;
      } else {
        res = add(res, 1);
        break;
      }
    }
    ans[i] = res;
  }
  for (int i = n; i; --i) {
    for (int j = 2 * i; j <= n; j += i) {
      ans[i] = sub(ans[i], ans[j]);
    }
  }
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    res = add(res, mul(ans[i], 2 * n / i));
  }
  cout << res;

  return 0;
}