Có $N$ viên đá được đánh số từ $1$ đến $N$, xếp thành một hàng theo thứ tự tăng dần. Mỗi viên đá có màu trắng hoặc đen. Trọng lượng của viên đá thứ $i$ là $A_i$.

Bạn sẽ lần lượt lấy đi từng viên đá cho đến khi không còn viên nào.

Khi lấy đi một viên đá, nếu nó không phải là viên ngoài cùng bên trái hoặc bên phải trong số tất cả các viên đá còn lại, đồng thời cả hai viên đá kề nó đều khác màu với nó, điểm số của bạn tăng thêm trọng lượng của viên đá được lấy đi. Hai viên đá được gọi là kề nhau nếu không có viên đá nào nằm giữa chúng.

Có $N!$ cách lấy đi tất cả các viên đá. Hãy tính tổng điểm số của tất cả các cách có thể, lấy modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($1 \le N \le 300\,000$).

Dòng thứ hai chứa một xâu $S$ có độ dài $N$, mỗi ký tự là B hoặc W. Ký tự thứ $i$ của $S$, ký hiệu là $S_i$, là B nếu viên đá thứ $i$ màu đen; ngược lại, $S_i$ là W và viên đá thứ $i$ màu trắng.

Dòng thứ ba chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ biểu thị trọng lượng của viên đá $i$.

Dữ liệu ra

In ra tổng điểm số của tất cả các cách lấy đá có thể, lấy modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

4
WBWB
6 4 5 3

Dữ liệu ra 1

72

Dữ liệu vào 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Dữ liệu ra 2

218304