题目描述

有 $N$ 块石子从左到右排成一列，编号为 $1,2,\ldots,N$。每块石子为黑色或白色，第 $i$ 块石子的重量为 $A_i$。

你会不断选择并取走一块尚未取走的石子，直到所有石子都被取走。

取走某块石子时，若同时满足以下条件，就获得等于该石子重量的分数：

1. 它不是当前剩余石子中最左边或最右边的一块；
2. 当前与它相邻的左右两块石子，颜色都与它不同。

若两块尚未取走的石子之间没有其他尚未取走的石子，则称它们当前相邻。

取走全部石子的顺序共有 $N!$ 种。请计算所有取法所得分数之和，并对 $998244353$ 取模。

输入格式

第一行包含整数 $N$。

第二行包含一个长度为 $N$ 的字符串 $S$：B 表示黑色，W 表示白色。

第三行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示石子的重量。

数据范围：

输出格式

输出所有 $N!$ 种取石顺序所得分数之和对 $998244353$ 取模的结果。

样例 1

输入

4
WBWB
6 4 5 3

输出

72

样例 2

输入

8
WBBWBWBB
6 4 8 2 5 3 1 5

输出

218304