$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, \dots, 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