$N$ камней, пронумерованных от $1$ до $N$, расположены в ряд в порядке возрастания номеров. Каждый камень окрашен в белый или чёрный цвет. Вес $i$-го камня равен $A_i$.

Вы будете удалять камни по одному, пока не удалите все камни.

Если при удалении камень не является ни самым левым, ни самым правым среди всех оставшихся камней и ни один из двух соседних с ним камней не совпадает с ним по цвету, ваш счёт увеличивается на вес удаляемого камня. Два камня являются соседними, если между ними нет других камней.

Существует $N!$ способов удалить все камни. Вычислите сумму результатов всех возможных способов по модулю $998\,244\,353$.

Входные данные

Первая строка содержит одно целое число $N$ ($1 \le N \le 300\,000$).

Вторая строка содержит строку $S$ длины $N$, каждый символ которой равен B или W. $i$-й символ строки $S$, обозначаемый $S_i$, равен B, если $i$-й камень чёрный; иначе $S_i$ равен W, а $i$-й камень белый.

Третья строка содержит $N$ целых чисел $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ обозначает вес камня $i$.

Выходные данные

Выведите сумму результатов всех возможных способов удаления камней по модулю $998\,244\,353$.

Примеры

Входные данные 1

4
WBWB
6 4 5 3

Выходные данные 1

72

Входные данные 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Выходные данные 2

218304