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 N = 2e5 + 5;
const int mod = 998244353;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); }
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }
int _w;

int n , f[N];
char str[N] , tmp[N];
bool mark[N];

int solve( int k ) {
  int res = 0;
  for( int i = 1 ; i <= k ; ++i )
    inc( res , pls( res , str[i] - '0' ) );
  for( int i = 1 , cur = 1 ; i <= n ; ++i , cur = cur == 2 * k ? 1 : cur + 1 ) 
    if( cur > k ) tmp[i] = str[cur - k] ^ 1;
    else tmp[i] = str[cur];
  for( int i = 1 ; i <= n ; ++i )
    if( tmp[i] ^ str[i] )
      return tmp[i] < str[i] ? pls( res , 1 ) : res;
  return pls( res , 1 );
}

int main( void ) {
  _w = scanf("%d%s",&n,str+1);
  for( int i = 1 ; i <= n ; ++i )
    if( n % i == 0 && ( ( n / i ) & 1 ) )
      f[i] = i * 2 , mark[i] = 1;
  for( int i = n - 1 ; i ; --i ) if( mark[i] )
    for( int j = i + i ; j <= n ; j += i ) if( mark[j] )
      dec( f[i] , f[j] );
  int ans = 0;
  for( int i = 1 ; i <= n ; ++i )
    if( mark[i] )
      inc( ans , 1LL * solve( i ) * f[i] % mod );
  cout << ans;
  return 0;
}
