$N$ pierres numérotées de $1$ à $N$ sont disposées en ligne dans l’ordre croissant. Chaque pierre est blanche ou noire. Le poids de la $i$-ème pierre est $A_i$.

Vous retirerez les pierres une par une jusqu’à ce qu’elles soient toutes retirées.

Lorsque vous retirez une pierre, si elle n’est ni la plus à gauche ni la plus à droite parmi toutes les pierres restantes, et qu’aucune des deux pierres qui lui sont adjacentes n’a la même couleur qu’elle, votre score augmente du poids de la pierre retirée. Deux pierres sont adjacentes s’il n’y a aucune pierre entre elles.

Il y a $N!$ façons possibles de retirer toutes les pierres. Calculez la somme des scores de toutes les façons possibles, modulo $998\,244\,353$.

Entrée

La première ligne contient un entier $N$ ($1 \le N \le 300\,000$).

La deuxième ligne contient une chaîne $S$ de longueur $N$, dont chaque caractère est B ou W. Le $i$-ème caractère de $S$, $S_i$, est B si la $i$-ème pierre est noire ; sinon, $S_i$ est W et la $i$-ème pierre est blanche.

La troisième ligne contient $N$ entiers $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ représente le poids de la pierre $i$.

Sortie

Affichez la somme des scores de toutes les façons possibles de retirer les pierres, modulo $998\,244\,353$.

Exemples

Entrée 1

4
WBWB
6 4 5 3

Sortie 1

72

Entrée 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Sortie 2

218304