22879번 - 돌 가져가기 2

$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다. 

돌들을 왼쪽부터 1번 돌, 2번 돌,..., $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.

당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.

돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.

돌을 가져가는 방법은 순서에 따라 총 $N!$가지 서로 다른 방법이 존재한다. 가능한 $N!$가지 방법에서 얻을 수 있는 점수의 총합을 구하여라.

첫 줄에 양의 정수 $N$이 주어진다. ($1 \le N \le 2 \times 10^5$)

둘째 줄에 B 또는 W로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

$S$의 $i$번째 문자 $S_i$는 왼쪽에서 $i$번째 돌의 색을 나타낸다. B는 돌이 검은색임을, W는 돌이 흰색임을 뜻한다.

셋째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어진다. ($1 \le A_i \le 10^9$)

$A_i$ 는 $i$번 돌의 무게를 나타낸다. 

첫째 줄에 $N!$가지 방법에서 얻을 수 있는 점수의 총합을 $998\ 244\ 353$으로 나눈 나머지를 출력한다.

왼쪽에서 두 번째 돌을 가져가면서 점수를 얻는 방법과 세 번째 돌을 가져가면서 점수를 얻는 방법이 각각 8가지씩 있다. 따라서 총 점수는 $8 \times 4 + 8 \times 5 = 72$ 점이다.