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>
#define DIM 200005
#define mod 998244353
using namespace std;
int n, i, sol, j, sum, ok;
char s[DIM], s2[DIM], ff[DIM];
int v[DIM];
int main(){
    cin>> n;
    cin>> s + 1;
    for(i = 1; i <= n; i++){
        if(n % i == 0 && (n / i) % 2 == 1){
            ff[i] = 1;
            sum = 0;
            for(j = 1; j <= i; j++){
                sum = (sum * 2 + s[j] - '0') % mod;
            }
            ok = 1;
            for(j = 1; j <= i; j++){
                s2[j] = s[j];
            }
            for(j = i + 1; j <= n; j++){
                s2[j] = '0' + '1' - s2[j - i];
            }
            for(j = 1; j <= n; j++){
                if(s2[j] != s[j]){
                    if(s2[j] < s[j]){
                        break;
                    }
                    else{
                        ok = 0;
                        break;
                    }
                }
            }
            sum = (sum + ok) % mod;
            v[i] = sum;
        }
    }
    for(i = 1; i <= n; i++){
        if(ff[i] == 0){
            continue;
        }
        for(j = i + i; j <= n; j += i){
            v[j] = (mod + v[j] - v[i]) % mod;
        }
        sol = (sol + v[i] * 2LL * i) % mod;
    }
    cout<< sol;
}
