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;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;


int main() {
    ll n;
    string s;
    cin >> n >> s;
    reverse(s.begin(),s.end());
    vector<ll> a(0);
    rep(i,n-1){
        if ((n-i-1)%((i+1)*2)==0) a.push_back(i+1);
    }
    ll ans=0,m=1;
    rep(i,s.size()){
        if (s[i]=='1') (ans+=m)%=mod;
        (m*=2)%=mod;
    }
    (ans+=1)%=mod;
    (ans*=(n*2))%=mod;
    reverse(s.begin(),s.end());
    vector<ll> h(a.size());
    rep(i,a.size()){
        // cout << o << endl;
        ll p=0,mm=1;
        rep(j,a[i]){
            if (s[a[i]-1-j]=='1') (p+=mm)%=mod;
            (mm*=2)%=mod;
        }
        // cout << nn << endl;
        bool r=true;
        int rr=0;
        for (int j=a[i];j<n;j++){
            if (j%a[i]==0) rr=1-rr;
            int f=s[j]-'0',g=s[j%a[i]]-'0';
            if (rr) g=1-g;
            if (f>g) break;
            if (g>f) {
                r=false;
                break;
            }
        }
        if (r) p=(p+1)%mod;
        rep(j,i){
            if (a[i]%a[j]==0) p=(p+mod-h[j])%mod;
        }
        h[i]=p;
        // cout << p << endl;
        ll w=(p*a[i]*2)%mod;
        ans=(ans+mod-(p*n*2-w)%mod)%mod;
        // cout << w << endl;
    }
    cout << ans << endl;
}
