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;
const LL NS = (LL)2e5 + 4, MOD = 998244353;
LL N;
LL arr[NS];
LL val[NS];

int main(){
    scanf("%lld", &N);
    LL ans = 0, st = -1;
    for(LL i = 1; i <= N; ++i){
        scanf("%1d", arr + i);
    }
    int last = 0;
    for(int j = 1; j <= N; ++j){
        if(arr[j]) last = j;
        if(N % j == 0 && N / j % 2){
            LL cnt = 0;
            for(int x = 1; x <= j; ++x){
                cnt *= 2;
                cnt += arr[x];
                cnt %= MOD;
            }
            ++cnt;
            int A = (int)1e9, B = (int)1e9;
            for(int x = 1; x <= j; ++x){
                for(int y = x, z = arr[x]; y <= N; y += j, z ^= 1){
                    if(arr[y] < z){
                        A = min(A, y);
                    }
                    else if(arr[y] > z){
                        B = min(B, y);
                    }
                }
            }
            cnt -= B > A; if(cnt < 0) cnt += MOD;
            for(int x = 1; x * x <= j; ++x){
                if(j % x == 0){
                    cnt -= val[x];
                    if(x * x < j) cnt -= val[j / x];
                    while(cnt < 0) cnt += MOD;
                }
            }
            val[j] = cnt;
            ans += cnt * j * 2;
            ans %= MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
