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>
#include <vector>
#include <string>

using namespace std;

const int MOD = 998244353;

int main(){
    long long N;
    string S;
    while(cin >> N >> S){
        vector<long long> dig(N+1, 0);
        for(int i=0;i<N;i++) dig[i+1] = (2*dig[i]+S[i]-'0')%MOD;
        vector<long long> key;
        vector<long long> num;
        long long res = 0;
        for(int div=(N-1)/2*2+1;div>=1;div-=2){
            if(N%div) continue;
            const long long d = N/div;
            long long cur = dig[d];
            bool ok = true;
            for(int i=0;i<N;i++){
                int cmp = S[i%d] - '0';
                if(i/d%2) cmp = 1 - cmp;
                if(S[i] - '0' < cmp) ok = false;
                else if(S[i] - '0' > cmp) break;
            }
            if(ok) cur = (cur+1) % MOD;
            for(int i=0;i<key.size();i++){
                if(d%key[i] == 0) cur = (cur + MOD - num[i]) % MOD;
            }
            key.push_back(d);
            num.push_back(cur);
            res = (res + 2 * d * cur) % MOD;
        }
        cout << res << endl;
    }
}