$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