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
# -*- coding: utf-8 -*-
"""
Created on Sat Oct  5 21:16:35 2019

@author: 23374
"""

from math import *
P = 998244353

n = int(input())
num = int(input(),2) + 1

a = []

for i in range(2,int(sqrt(2*n))+1):
    if 2*n%i==0 :
        a.append(i)

b = a.copy()
b.reverse()
for x in b:
    if(x*x!=2*n):
        a.append(2*n//x)

def expgcd(x,x1,y,y1):
    if x<y :
        x, x1, y, y1 = y, y1, x, x1
    if y==0 :
        return (x,x1) if y1==-1 else (0,0)
    if y1==-1:
        return expgcd(x%y,x1,y,y1)
    else:
        c = -x1 if (x // y) % 2 == 1 else x1
        return expgcd(x%y,c,y,y1)

f = []
for k in a:
    x = expgcd(k,-1,n,1)
    f.append(0 if x == (0,0) else 2**x[0] + x[1])

Mnum = num % P
ans = Mnum * 2*n % P
g = [0] * len(a)
for i in range(len(a)):
    if (f[i]==0): continue
    x, y = a[i], num // ( (2**n+1) // f[i])
    for j in range(i):
        if (a[i]%a[j]==0) :
            y -= g[j]
    g[i] = y
    ans = (ans - y * (2*n - a[i]) ) % P

print( (ans+P) % P )