Yana, Mino, White, dan Huzz adalah sahabat karib.

Belakangan ini Mino merasa bingung. Terobsesi dengan kegagalan masa lalunya di OI, ia kesulitan merencanakan masa depannya sambil mengatur jadwal sekolahnya yang padat. Ketiga temannya menyarankan agar ia mengevaluasi tingkat kepentingan tugas-tugasnya dan memprioritaskannya.

Misalkan terdapat $n$ tugas berbeda yang dinomori dari $1$ sampai $n$. Setiap kali, Huzz memilih dua tugas yang bersebelahan, White membandingkan keduanya, dan Yana menggabungkannya menjadi satu tugas tunggal. Mino terkejut mendapati bahwa proses ini secara tidak sengaja membentuk sebuah pohon segmen (segment tree), yang tidak harus membelah tepat di tengah. Lebih tepatnya, proses ini membentuk sebuah pohon dengan $2n - 1$ simpul, di mana setiap subpohon bersesuaian dengan sebuah segmen berurutan. Perhatikan bahwa semua $n$ tugas adalah daun, sedangkan $n - 1$ simpul lainnya masing-masing memiliki dua anak. Simpul-simpul yang dihasilkan dari perbandingan ini menentukan nilai sisi menuju anak-anaknya: $0$ untuk yang lebih kecil dan $1$ untuk yang lebih besar.

Mino sangat gemar berhitung. Ia mendefinisikan bobot dari setiap tugas sebagai jumlah XOR dari sisi-sisi sepanjang lintasan dari tugas tersebut menuju akar. Ia bertanya-tanya: jika bobot-bobotnya diberikan, ada berapa banyak cara untuk membangun pohon seperti itu dan membandingkan anak-anaknya?

Sekali lagi, Mino tidak mahir dalam OI, itulah sebabnya ia meminta bantuan Anda. Untuk menyederhanakan masalah, Anda hanya perlu mencari jawabannya modulo $998,244,353$.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat positif $n$ ($1 \le n \le 250000$), yaitu banyaknya tugas.

Baris kedua berisi sebuah string biner $S$ dengan panjang $n$, di mana $S_i$ menyatakan Bitwise-XOR dari semua nilai pada sisi dari tugas $i$ menuju akar.

Keluaran

Cetak sebuah bilangan bulat, yaitu jawabannya modulo $998,244,353$.

Contoh

Masukan

4
0101

Keluaran

6

Catatan

Terdapat $6$ cara untuk membangun pohon dan membandingkan anak-anaknya: