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 all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=400005;
const ll INF=1LL<<55;
ll dp[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    string S;cin>>S;
    
    for(ll i=1;i<=2*N;i++){
        if(2*N%i!=0||(2*N/i)%2==0) continue;
        
        ll sum=0;
        for(int j=0;j<i/2;j++){
            sum*=2;
            if(S[j]=='1') sum++;
            
            sum%=mod;
        }
        
        string A=S.substr(0,i/2);
        string B=A;
        for(int j=0;j<i/2;j++){
            if(B[j]=='0') B[j]='1';
            else B[j]='0';
        }
        
        string T=A;
        while(T.size()<S.size()){
            T+=B;
            T+=A;
        }
        
        if(T<=S) sum++;
        
        for(int j=1;j<i;j++){
            if(i%j==0){
                sum+=mod-dp[j];
                sum%=mod;
            }
        }
        
        dp[i]=sum;
    }
    
    ll ans=0;
    
    for(ll i=1;i<=2*N;i++){
        ans+=dp[i]*i;
        ans%=mod;
    }
    
    cout<<ans<<endl;
}

