409924: GYM103855 G Stones 2

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Stones 2time limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

$$$N$$$ stones labeled from $$$1$$$ to $$$N$$$ are arranged in a row in increasing order. Each stone is colored either white or black. The weight of the $$$i$$$-th stone is $$$A_i$$$.

You will remove the stones one at a time until all the stones are removed.

When removing a stone, if the stone is not the leftmost or rightmost of all remaining stones, and neither stone adjacent to the stone being removed matches it in color, your score increases by the weight of the stone being removed. Two stones are adjacent if there are no stones in between those two.

There are $$$N!$$$ possible ways to remove all the stones. Compute the sum of scores from each possible way, modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 300\, 000$$$).

The second line contains a string $$$S$$$ of length $$$N$$$ where each character is either B or W. The $$$i$$$th character of $$$S$$$, $$$S_i$$$, is B if the $$$i$$$-th stone is black, otherwise, $$$S_i$$$ is W and the $$$i$$$-th stone is white.

The third line contains $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ ($$$1 \le A_i \le 10^9$$$). $$$A_i$$$ represents the weight of stone $$$i$$$.

Output

Output the sum of the scores over all possible ways to take the stones, modulo $$$998\,244\,353$$$.

ExamplesInput
4
WBWB
6 4 5 3
Output
72
Input
8
WBBWBWBB
6 4 8 2 5 3 1 5
Output
218304

加入题单

上一题 下一题 算法标签: