Flipping Segments in a Binary String

You are given a binary string S of length n (i.e. S contains only the characters 0 and 1). You must perform exactly n operations. In each operation, you choose two indices l and r such that \(1 \le l < r \le n\), and then flip every bit in the substring \(S[l\dots r]\). Flipping a bit means turning 0 into 1 and 1 into 0.

Let the initial string be \(S\) and let an operation be represented by its characteristic vector \(v_{l,r}\) where \[ v_{l,r} = (\underbrace{1,\ldots,1}_{r-l+1},0,\ldots,0) \quad (\text{with ones in positions } l \text{ to } r) . \] After performing the operations, the final string is obtained by taking the bitwise XOR (modulo 2) of \(S\) with the XOR-sum of all the chosen segment vectors. Since each operation is its own inverse, the order does not matter and only the parity (odd or even number) of times each segment is flipped affects the result.

It turns out that regardless of S, the number of distinct strings that can be obtained depends only on n. In fact one may show that the answer is given by \[ \text{answer} = \begin{cases} 2^{n-1} \pmod{998244353} & \text{if } n \text{ is odd},\\ 2^{n-2} \pmod{998244353} & \text{if } n \text{ is even}. \end{cases} \]

Compute the number of different strings possible after exactly n operations, modulo 998244353.

inputFormat

The first line contains a single integer n (with n ≥ 2). The second line contains a binary string S of length n consisting only of characters 0 and 1.

outputFormat

Output one integer — the number of distinct binary strings that can be obtained after performing exactly n operations, taken modulo 998244353.

sample

2
01

1