A 01 sequence is called good if and only if it can be reduced to an empty sequence by repeatedly applying the following operation:

• In each operation, you may choose a 0 and remove it along with the element immediately to its left, or choose a 1 and remove it along with the element immediately to its right. Note that you must remove exactly two elements in each operation. For example, you cannot choose the 0 in 011, nor can you choose the 1 in 001.

Here are some examples:

• A sequence like 0100 is good, because you can first choose the 1 to get 00, and then choose the second 0 to get an empty sequence.
• A sequence like 0101 is not good, because regardless of whether you choose the first 1 or the second 0, the sequence becomes 01.

Given a sequence containing only 0, 1, and ?, you need to calculate the sum of the number of ways to replace each ? with 0 or 1 such that the resulting 01 sequence is good, for every subsequence of the given sequence. Output the sum of all these answers modulo $998244353$.

Input

The input is read from standard input.

The input consists of two lines.

The first line contains a positive integer $n$.

The second line is a string of length $n$ containing only 0, 1, and ?.

Output

Output to standard output.

Output a single integer representing the sum of the answers as described in the problem, modulo $998244353$.

Examples

Input 1

4
1?1?

Output 1

16

Input 2

10
1?0?1?????

Output 2

8078

Constraints

For $10\%$ of the data, $n \le 8$.

For $50\%$ of the data, $n \le 5000$.

For all test data, $1 \le n \le 10^6$.