Taking Stones 2

$N$ stones are lined up in a row. Each stone is either white or black.

Number the stones from the left as stone 1, stone 2, ..., stone $N$. The weight of stone $i$ is $A_i$.

You will repeatedly pick one of the lined-up stones and take it, for a total of $N$ times, until every stone is gone.

When you take a stone, if that stone is neither the leftmost nor the rightmost among the stones currently lined up, and both stones adjacent to the stone you took have a color different from the stone you took, you gain a score equal to the weight of the stone you took.

There are $N!$ different ways to take the stones, depending on the order. Find the sum of the scores over all $N!$ possible ways.

The first line gives a positive integer $N$. ($1 \le N \le 2 \times 10^5$)

The second line gives a string $S$ of length $N$ consisting only of B and W.

The $i$-th character $S_i$ of $S$ is the color of the $i$-th stone from the left. B means the stone is black and W means the stone is white.

The third line gives $N$ integers $A_1, A_2, \cdots, A_N$. ($1 \le A_i \le 10^9$)

$A_i$ is the weight of stone $i$.

On the first line, print the sum of the scores over all $N!$ ways, modulo $998\ 244\ 353$.

There are 8 ways that gain a score by taking the second stone from the left, and 8 ways that gain a score by taking the third stone. So the total score is $8 \times 4 + 8 \times 5 = 72$ points.