$N$ kamieni ponumerowanych od $1$ do $N$ ułożono w rzędzie w rosnącej kolejności numerów. Każdy kamień jest biały albo czarny. Waga $i$-tego kamienia wynosi $A_i$.

Będziesz usuwać kamienie pojedynczo, aż wszystkie zostaną usunięte.

Jeśli podczas usuwania kamień nie jest ani najbardziej lewym, ani najbardziej prawym spośród wszystkich pozostałych kamieni, a żaden z dwóch sąsiednich kamieni nie ma takiego samego koloru jak usuwany kamień, twój wynik zwiększa się o wagę usuwanego kamienia. Dwa kamienie są sąsiednie, jeśli nie ma między nimi innych kamieni.

Istnieje $N!$ sposobów usunięcia wszystkich kamieni. Oblicz sumę wyników ze wszystkich możliwych sposobów modulo $998\,244\,353$.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $N$ ($1 \le N \le 300\,000$).

Drugi wiersz zawiera napis $S$ długości $N$, którego każdy znak to B lub W. $i$-ty znak napisu $S$, oznaczony $S_i$, to B, jeśli $i$-ty kamień jest czarny; w przeciwnym razie $S_i$ to W, a $i$-ty kamień jest biały.

Trzeci wiersz zawiera $N$ liczb całkowitych $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ oznacza wagę kamienia $i$.

Wyjście

Wypisz sumę wyników dla wszystkich możliwych sposobów usuwania kamieni modulo $998\,244\,353$.

Przykład

Wejście 1

4
WBWB
6 4 5 3

Wyjście 1

72

Wejście 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Wyjście 2

218304