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;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=998244353;
const double pi=3.1415926535897932,eps=1e-6;
int n,ans;
vector<pii > fact;string t,x,ss,rev;
int main()
{
    fastio;cin>>n>>x;
    rep(i,1,2*n){
        if(2*n%i!=0||n%i==0) continue;
        int cur=0,len=i/2;
        rap(j,0,fact.size()){
            if(i%fact[j].fi==0) cur=(cur-fact[j].se+mod)%mod;
        }
        int w=1;
        per(j,len,1){
            if(x[j-1]=='1') cur=(cur+w)%mod;
            //cout<<i<<" "<<cur<<'\n';
            w=(w*2)%mod;
        }
        ss=x.substr(0,len);rev=ss;
        rap(i,0,rev.size()) rev[i]=(rev[i]=='0'?'1':'0');
        t="";rep(j,1,2*n/i) {
            if(j&1) t+=ss;
            else t+=rev;
        }
        if(t<=x) cur=(cur+1)%mod;
        fact.pb(mpr(i,cur));
    }
    rap(i,0,fact.size()) ans=(ans+(ll)fact[i].se*fact[i].fi%mod)%mod;
    cout<<ans<<'\n';
    return 0;
}