Sebanyak $N$ batu berlabel $1$ hingga $N$ disusun dalam satu baris dengan urutan label menaik. Setiap batu berwarna putih atau hitam. Berat batu ke-$i$ adalah $A_i$.

Anda akan mengambil batu satu per satu hingga semua batu telah diambil.

Ketika mengambil sebuah batu, jika batu tersebut bukan yang paling kiri maupun paling kanan di antara semua batu yang tersisa, dan kedua batu yang bersebelahan dengannya memiliki warna yang berbeda darinya, skor Anda bertambah sebesar berat batu yang diambil. Dua batu bersebelahan jika tidak ada batu lain di antara keduanya.

Ada $N!$ cara yang mungkin untuk mengambil semua batu. Hitung jumlah skor dari semua cara yang mungkin, modulo $998\,244\,353$.

Masukan

Baris pertama berisi sebuah bilangan bulat $N$ ($1 \le N \le 300\,000$).

Baris kedua berisi sebuah string $S$ sepanjang $N$ yang setiap karakternya adalah B atau W. Karakter ke-$i$ dari $S$, yaitu $S_i$, adalah B jika batu ke-$i$ berwarna hitam; jika tidak, $S_i$ adalah W dan batu ke-$i$ berwarna putih.

Baris ketiga berisi $N$ bilangan bulat $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le 10^9$). $A_i$ menyatakan berat batu $i$.

Keluaran

Keluarkan jumlah skor untuk semua cara yang mungkin dalam mengambil batu, modulo $998\,244\,353$.

Contoh

Masukan 1

4
WBWB
6 4 5 3

Keluaran 1

72

Masukan 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Keluaran 2

218304