$N$ pedras numeradas de $1$ a $N$ estão dispostas numa fila por ordem crescente. Cada pedra é branca ou preta. O peso da $i$-ésima pedra é $A_i$.

Vais retirar as pedras uma de cada vez até todas terem sido retiradas.

Ao retirar uma pedra, se ela não for a mais à esquerda nem a mais à direita de todas as pedras restantes, e nenhuma das duas pedras adjacentes tiver a mesma cor que ela, a tua pontuação aumenta pelo peso da pedra retirada. Duas pedras são adjacentes se não houver pedras entre elas.

Existem $N!$ formas possíveis de retirar todas as pedras. Calcula a soma das pontuações de todas as formas possíveis, módulo $998\,244\,353$.

Entrada

A primeira linha contém um único inteiro $N$ ($1 \le N \le 300\,000$).

A segunda linha contém uma cadeia $S$ de comprimento $N$, em que cada carácter é B ou W. O $i$-ésimo carácter de $S$, $S_i$, é B se a $i$-ésima pedra for preta; caso contrário, $S_i$ é W e a $i$-ésima pedra é branca.

A terceira linha contém $N$ inteiros $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ representa o peso da pedra $i$.

Saída

Imprime a soma das pontuações de todas as formas possíveis de retirar as pedras, módulo $998\,244\,353$.

Exemplos

Entrada 1

4
WBWB
6 4 5 3

Saída 1

72

Entrada 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Saída 2

218304