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 M = 998244353;

int Count(int p, string s) {
    int n = s.size();
    assert(n%p == 0);
    int ans = 0;
    for (int i=0; i<p; i++)
        ans = (ans*2 + s[i]-'0')%M;

    string t(s.begin(), s.begin()+p);
    for (int i=p; i<n; i++) {
        t += '0' + ('1' - t[i-p]);
    }
//    cout<<p<<" "<<ans<<" "<<t<<endl;
    return (ans + (t<=s))%M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    string s;
    cin>>s;

    vector<pair<int,int>> prs;

    for (int i=1; i<=2*n; i++) {
        if ((2*n)%i)    continue;
        if (n%i==0)     continue;
        int p = i/2;
        int cnt = Count(p, s);

        prs.emplace_back(i, cnt);
//        cout<<i<<" "<<cnt<<endl;
    }

    long long ans = 0;
    long long total = 0;

    for (int i=0; i<prs.size(); i++) {
        ans = (ans + 1LL*prs[i].first*prs[i].second)%M;
        for (int j=i+1; j<prs.size(); j++) {
            if (prs[j].first%prs[i].first == 0) {
                prs[j].second = (prs[j].second + M - prs[i].second)%M;
            }
        }
        total += prs[i].second;
    }
//    cout<<total<<endl;
    cout<<ans<<endl;
}
