$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