Hay $N$ piedras numeradas del $1$ al $N$, dispuestas en una fila en orden creciente. Cada piedra es blanca o negra. El peso de la piedra $i$ es $A_i$.

Quitarás las piedras de una en una hasta haberlas quitado todas.

Al quitar una piedra, si no es la situada más a la izquierda ni más a la derecha entre todas las piedras restantes, y ninguna de las dos piedras adyacentes tiene su mismo color, tu puntuación aumenta en el peso de la piedra que quitas. Dos piedras son adyacentes si no hay ninguna piedra entre ellas.

Hay $N!$ formas posibles de quitar todas las piedras. Calcula la suma de las puntuaciones de todas las formas posibles, módulo $998\,244\,353$.

Entrada

La primera línea contiene un único entero $N$ ($1 \le N \le 300\,000$).

La segunda línea contiene una cadena $S$ de longitud $N$, en la que cada carácter es B o W. El carácter $i$ de $S$, $S_i$, es B si la piedra $i$ es negra; en caso contrario, $S_i$ es W y la piedra $i$ es blanca.

La tercera línea contiene $N$ enteros $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ representa el peso de la piedra $i$.

Salida

Imprime la suma de las puntuaciones de todas las formas posibles de quitar las piedras, módulo $998\,244\,353$.

Ejemplos

Entrada 1

4
WBWB
6 4 5 3

Salida 1

72

Entrada 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Salida 2

218304