ก้อนหิน $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