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;
typedef pair<int,int> P;
ll const mod = 998244353;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = n*2;
    ll b = 1;
    unordered_map<int,ll> mp;
    for (int i = n-1;i >= 0;--i) {
        if (s[i] == '1') (ans += 2*b*n) %= mod;
        (b *= 2) %= mod;
    }
    for (int x = n/2*2+1;x > 2;x -= 2)  if (n%x == 0) {
        b = 1;
        ll cnt = 0;
        for (int i = n/x-1;i >= 0;--i) {
            if (s[i] == '1') (cnt += b) %= mod;
            (b *= 2) %= mod;
        }
        string t = "",u = s.substr(0,n/x),revu = "";
        for (int i = 0;i < n/x;++i) {
            if (s[i] == '1') revu += '0';
            else revu += '1';
        }
        for (int i = 0;i < x;++i) {
            if (i&1) t += revu;
            else t += u;
        }
        if (t <= s) cnt++;
        (cnt -= mp[x]) %= mod;
        (ans -= (n*2-n*2/x)*cnt%mod) %= mod;
        for (int i = x-2;i > 2;i -= 2) if (x%i == 0 && n%i == 0) (mp[i] += cnt) %= mod;
    }
    cout << (ans+mod)%mod << endl;
}