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
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)998244353

ll N;
char X[202020];
ll mk[202020];
ll pow2[202020];
ll i, j, k,ans;



int main(){
    scanf("%lld%s", &N,X);
    j = 1;
    ans = 1;
    pow2[0] = 1;
    fornum(i,0,N){
        if(X[N-i-1]=='1'){
            ans = (ans + j) % MOD;
        }
        j = j * 2 % MOD;
        pow2[i + 1] = j;
    }
    //printf("%lld %lld\n", ans,ans*2*N%MOD);
    ans = ans * 2 * N % MOD;
    //printf("%lld\n", ans);
    fornum(i,1,N){
        
        if(N%i||N/i%2==0)
            continue;
        k = N / i;
        ll aa = (MOD - mk[i]) % MOD;
        fornum(j,0,i){
            if(X[j]=='1'){
                aa = (aa + pow2[i - j - 1]) % MOD;
            }
        }
        
        fornum(j,0,N){
            if((X[j%i]=='1')^(j/i%2)!=('1'==X[j])){
                if(X[j]=='1')
                    aa++;
                break;
            }
        }
        if(j==N)
            aa++;
        ans = (ans + (MOD - 2 * N + i*2)*aa) % MOD;
        for (j = i*2; j <= N;j+=i){
            mk[j] = (mk[j] + aa) % MOD;
        }
    }
    printf("%lld", ans);

    return 0;
}