توجد $N$ حجارة مرقمة من $1$ إلى $N$، مرتبة في صف بترتيب تصاعدي. كل حجر أبيض أو أسود. وزن الحجر رقم $i$ هو $A_i$.

ستزيل الحجارة واحدًا تلو الآخر حتى تتم إزالة جميع الحجارة.

عند إزالة حجر، إذا لم يكن الحجر الأيسر أو الأيمن بين جميع الحجارة المتبقية، ولم يكن أي من الحجرين المجاورين له من لونه نفسه، فإن نتيجتك تزداد بمقدار وزن الحجر الذي تزيله. يكون حجران متجاورين إذا لم توجد حجارة بينهما.

توجد $N!$ طريقة ممكنة لإزالة جميع الحجارة. احسب مجموع النتائج لجميع الطرق الممكنة، بترديد $998\,244\,353$.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $N$ ($1 \le N \le 300\,000$).

يحتوي السطر الثاني على سلسلة $S$ طولها $N$، وكل محرف فيها هو B أو W. المحرف رقم $i$ من $S$، أي $S_i$، هو B إذا كان الحجر رقم $i$ أسود؛ وإلا فإن $S_i$ هو W ويكون الحجر رقم $i$ أبيض.

يحتوي السطر الثالث على $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