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<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#define mod 998244353
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod

ll po(ll x,ll y){
    ll res=1;
    for(;y;y>>=1){
	if(y&1)mul(res,x);
	mul(x,x);
    }
    return res;
}

ll n;
string s;

ll f[200010];
void solve(ll m){
    ll res=0;
    for(int i=0;i<m;i++){
	if(s[i]=='1')mad(res,po(2,(m-i-1)));
    }
    bool ok=1;
    for(int i=0;i<n;i++){
	ll p=i%(2*m);
	char c;
	if(p<m)c=s[p];
	else c='0'+(s[p-m]=='0');
	
	if(s[i]<c)ok=0;
	if(s[i]!=c)break;
    }
    res+=ok;
    
    for(int i=1;i<m;i++){
	if(m%i==0)mad(res,-f[i]);
    }
    res%=mod;
    if(res<0)res+=mod;
    f[m]=res;
}

int main(){
    cin>>n>>s;
    ll ans=0;
    for(int i=1;i<=n;i++){
	if(n%i==0&&(n/i)%2==1){
	    solve(i);
	    mad(ans,i*f[i]);
	}
    }
    mul(ans,2);
    cout<<ans<<endl;
}

