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
def change(s):
    ans = []
    for i in s:
        if i== "0":
            ans.append("1")
        else:
            ans.append("0")
    return "".join(ans)

n = int(input())
s = input()
MOD = 998244353

# 重複込みで数える
a = [0] * (n+1)
for i in range(1, n + 1):
    if n % i == 0:
        a[i] += int(s[0:i], 2)
        a[i] %= MOD
        si = int(s[0:i])
        change_si = int(change(s[0:i]))
        for j in range(n // i):
            if j % 2 == 0:
                if si < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break
                if si > int(s[j*i:(j+1)*i]):
                    break
            else:
                if change_si < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break      
                if change_si > int(s[j*i:(j+1)*i]):
                    break 
        else:
            a[i] += 1

# 約数包除で重複を除く
for i in range(1, n + 1):
    for j in range(2*i, n + 1, i):
        if n % j == 0:
            a[j] -= a[i]

# b:有効周期
b = []
ans = 0
for i in range(1, n+1):
    if n % i == 0:
        if (n // i) % 2 == 1: 
                b.append(i)

#周期の重みを足し合わせる
for i in range(1, n+1):
    if n % i == 0:
        for tmp in b:
            if tmp % i == 0:
                ans += a[i] * 2*tmp
                ans %= MOD
                break
          
print(ans % MOD)

