Yana, Mino, White y Huzz son mejores amigos.

Mino se ha sentido confundido últimamente. Obsesionado con sus fracasos pasados en la OI, ha estado luchando por planificar su futuro mientras gestiona su apretada agenda escolar. Sus tres amigos le sugirieron que evaluara la importancia de sus tareas y las priorizara.

Supongamos que hay $n$ tareas diferentes numeradas de $1$ a $n$. Cada vez, Huzz selecciona dos tareas adyacentes, White las compara y Yana las fusiona en una sola tarea. A Mino le sorprende descubrir que este proceso forma accidentalmente un árbol de segmentos, que no necesariamente se divide por la mitad. Más precisamente, forma un árbol con $2n - 1$ nodos, donde cada subárbol corresponde a un segmento contiguo. Observa que las $n$ tareas son hojas, mientras que los otros $n - 1$ nodos tienen cada uno dos hijos. Estos nodos, que resultan de las comparaciones, definen los valores de las aristas hacia sus hijos: $0$ para el menor y $1$ para el mayor.

A Mino le gustan mucho los cálculos. Define el peso de cada tarea como la suma XOR de las aristas a lo largo del camino desde la tarea hasta la raíz. Se pregunta: si se dan los pesos, ¿de cuántas maneras se pueden construir dichos árboles y comparar a los hijos?

Una vez más, Mino no es hábil en la OI, razón por la cual ha recurrido a ti en busca de ayuda. Para simplificar el problema, solo necesitas encontrar la respuesta módulo $998,244,353$.

Entrada

La primera línea de la entrada contiene un entero positivo $n$ ($1 \le n \le 250000$), el número de tareas.

La segunda línea contiene una cadena binaria $S$ de longitud $n$, donde $S_i$ representa el XOR bit a bit (Bitwise-XOR) de todos los valores en las aristas desde la tarea $i$ hasta la raíz.

Salida

Imprime un entero, la respuesta módulo $998,244,353$.

Ejemplo

Entrada

4
0101

Salida

6

Nota

Hay $6$ maneras de construir el árbol y comparar a los hijos: