$N$ 顆標號從 $1$ 到 $N$ 的石子按標號遞增的順序排成一列。每顆石子都是白色或黑色。第 $i$ 顆石子的重量為 $A_i$。

你將逐一移除石子，直到所有石子都被移除。

移除一顆石子時，如果它不是所有剩餘石子中最左邊或最右邊的石子，而且與它相鄰的兩顆石子顏色都與它不同，你的分數就會增加被移除石子的重量。如果兩顆石子之間沒有其他石子，則稱它們相鄰。

移除所有石子共有 $N!$ 種可能的方式。計算每種方式所得分數的總和，並對 $998\,244\,353$ 取模。

輸入格式

第一行包含一個整數 $N$（$1 \le N \le 300\,000$）。

第二行包含一個長度為 $N$ 的字串 $S$，其中每個字元都是 B 或 W。如果第 $i$ 顆石子是黑色，則 $S$ 的第 $i$ 個字元 $S_i$ 是 B；否則 $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