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
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
char s[200007];
int mi2[200007],num[200007];
const int mod = 998244353;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n>>s;
    mi2[0]=1;
    for(int i=1;i<=n;++i)
        mi2[i]=2ll*mi2[i-1]%mod;
    for(int i=1;i<=n;i+=2)if(n%i==0){
        int length=n/i;
        bool flag=1;
        for(int j=0;j<n&&flag;++j){
            if(s[j]=='1'){
                if(j<length||s[j-length]=='1'){
                    num[length]=(num[length]+(j<length?mi2[length-j-1]:1))%mod;
                }
            }
            if(j>=length&&s[j]==s[j-length])
                flag=0;
        }
        if(flag)
            num[length]=(num[length]+1)%mod;
    }
    int ans=0;
    for(int i=1;i<=n;++i)if(n%i==0&&(n/i)&1&&num[i]){
        ans=(ans+2ll*num[i]*i)%mod;
        for(int j=i*2;j<=n;j+=i)
            num[j]=(num[j]+mod-num[i])%mod;
    }
    cout<<ans;
    return 0;
}
