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
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(readline())
X = read().rstrip().decode('utf-8')

def F(d):
    """
    ・dは奇数
    ・d個のブロックに分けられるものの個数
    """
    L = N//d
    arr = [int(X[i:i+L],2) for i in range(0,N,L)]
    cnt = arr[0] # 最初の桁が下回るもの
    x = arr[0] # 最初の桁がちょうどx。満たすか確認する。
    flip_x = ((1<<L)-1)^x
    bl = True
    for i,y in enumerate(arr):
        if i&1:
            if y > flip_x:
                break
            elif y == flip_x:
                continue
            else:
                bl = False
                break
        if y > x:
            break
        elif y == x:
            continue
        else:
            bl = False
            break
    return cnt + bl

# 奇数の約数を取得
div = set(x for x in range(1,1000) if N%x == 0)
div |= set(N//x for x in div)
div = sorted(d for d in div if d&1)

cnt = [F(d) for d in div]

# 包除を雑にやる
D = len(div)
for n in range(D-1,-1,-1):
    for m,d in enumerate(div[:n]):
        if div[n]%d == 0:
            cnt[m] -= cnt[n]

answer = sum((N//x)*y for x,y in zip(div,cnt))*2
answer %= MOD
print(answer)