$N$ Steine mit den Nummern $1$ bis $N$ sind in aufsteigender Reihenfolge in einer Reihe angeordnet. Jeder Stein ist entweder weiß oder schwarz. Das Gewicht des $i$-ten Steins ist $A_i$.

Du entfernst die Steine einzeln, bis alle Steine entfernt sind.

Wenn du einen Stein entfernst, der weder der äußerste linke noch der äußerste rechte aller verbleibenden Steine ist, und keiner seiner beiden benachbarten Steine dieselbe Farbe wie er hat, erhöht sich deine Punktzahl um das Gewicht des entfernten Steins. Zwei Steine sind benachbart, wenn zwischen ihnen keine anderen Steine liegen.

Es gibt $N!$ Möglichkeiten, alle Steine zu entfernen. Berechne die Summe der Punktzahlen aller Möglichkeiten modulo $998\,244\,353$.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$ ($1 \le N \le 300\,000$).

Die zweite Zeile enthält eine Zeichenkette $S$ der Länge $N$, in der jedes Zeichen entweder B oder W ist. Das $i$-te Zeichen von $S$, $S_i$, ist B, wenn der $i$-te Stein schwarz ist; andernfalls ist $S_i$ gleich W und der $i$-te Stein weiß.

Die dritte Zeile enthält $N$ ganze Zahlen $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ bezeichnet das Gewicht des Steins $i$.

Ausgabe

Gib die Summe der Punktzahlen aller möglichen Reihenfolgen zum Entfernen der Steine modulo $998\,244\,353$ aus.

Beispiele

Eingabe 1

4
WBWB
6 4 5 3

Ausgabe 1

72

Eingabe 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Ausgabe 2

218304