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
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=4e5 +10,mod=998244353;
const ll inf=1e18;

bool arr[maxn], is[maxn];
int tw[maxn];
vector<pii> v;

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

    tw[0]=1;
    for(int i=1;i<maxn;i++)
	tw[i]= 2ll*tw[i-1] %mod;
    int n; cin>>n;
    string s; cin>>s;

    int CNT=1, ans=0;
    for(int i=0;i<n;i++){
	CNT=(CNT + (s[i]=='1' ? tw[n-1-i] : 0 )) %mod;
    }
 
    for(int lp=1;lp<=n;lp++){
	if((2*n)%lp!=0) continue;
	if(n%lp == 0) continue;
	int k=lp/2;
	string ss;
	for(int i=0;i<n;i++){
	    ss+= '0' + ((s[i%k]=='1') ^ ((i/k)&1));
	}
	int cnt=1;
	for(int i=0;i<k;i++){
	    cnt= ( cnt + (s[i]=='1' ? tw[k-1-i] : 0)) %mod;
	}
	if(ss>s) cnt--;
	for(auto p:v){
	    if(lp%p.F==0)
		cnt=(cnt - p.S) %mod;
	}
	ans=(1ll*ans + 1ll*cnt*lp) %mod;
	v.PB({lp,cnt});
	CNT=(CNT - cnt) %mod;
    }
    ans=(1ll*ans + 1ll*CNT*2*n) %mod;
    if(ans<0) ans+=mod;
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
