$1$ から $N$ までの番号が付いた $N$ 個の石が、番号の昇順に一列に並んでいます。各石の色は白または黒です。$i$ 番目の石の重さは $A_i$ です。

すべての石がなくなるまで、石を一つずつ取り除きます。

石を取り除くとき、その石が残っているすべての石のうち左端でも右端でもなく、隣接するどちらの石も取り除く石とは異なる色であれば、取り除く石の重さだけ得点が増えます。二つの石の間に他の石がないとき、その二つの石は隣接しているといいます。

すべての石を取り除く方法は $N!$ 通りあります。それぞれの方法で得られる得点の総和を $998\,244\,353$ で割った余りを求めてください。

入力

最初の行には整数 $N$（$1 \le N \le 300\,000$）が与えられます。

次の行には長さ $N$ の文字列 $S$ が与えられます。各文字は B または W です。$S$ の $i$ 文字目 $S_i$ は、$i$ 番目の石が黒なら B、そうでなければ W であり、その石は白です。

次の行には $N$ 個の整数 $A_1,A_2,\ldots,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