Yana, Mino, White ja Huzz ovat parhaita ystäviä.

Mino on tuntenut olonsa hämmentyneeksi viime aikoina. Menneiden OI-epäonnistumistensa vaivaamana hänellä on ollut vaikeuksia suunnitella tulevaisuuttaan samalla, kun hän yrittää selviytyä kiireisestä kouluaikataulustaan. Hänen kolme ystäväänsä ehdottivat, että hän arvioisi tehtäviensä tärkeyden ja asettaisi ne tärkeysjärjestykseen.

Oletetaan, että on $n$ erilaista tehtävää, jotka on numeroitu $1$:stä $n$:ään. Joka kerta Huzz valitsee kaksi vierekkäistä tehtävää, White vertaa niitä ja Yana yhdistää ne yhdeksi tehtäväksi. Mino yllättyy huomatessaan, että tämä prosessi muodostaa vahingossa segmenttipuun, joka ei välttämättä jakaudu keskeltä. Tarkemmin sanottuna se muodostaa $2n - 1$ solmun puun, jossa jokainen alipuu vastaa yhtenäistä väliä. Huomaa, että kaikki $n$ tehtävää ovat lehtiä, kun taas muilla $n - 1$ solmulla on kullakin kaksi lasta. Nämä vertailuista syntyvät solmut määrittelevät lapsiinsa johtavien kaarien arvot: $0$ pienemmälle ja $1$ suuremmalle.

Mino pitää kovasti laskemisesta. Hän määrittelee jokaisen tehtävän painon tehtävästä juureen kulkevan polun kaarien XOR-summaksi. Hän pohtii: jos painot on annettu, kuinka monella tavalla tällaiset puut voidaan muodostaa ja lapset vertailla?

Mino ei taaskaan ole taitava OI:ssa, minkä vuoksi hän on kääntynyt puoleesi saadakseen apua. Tehtävän yksinkertaistamiseksi sinun tarvitsee vain etsiä vastaus modulo $998,244,353$.

Syöte

Syötteen ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$ ($1 \le n \le 250000$), tehtävien lukumäärän.

Toinen rivi sisältää pituuden $n$ binäärimerkkijonon $S$, missä $S_i$ kuvaa tehtävästä $i$ juureen johtavien kaarien kaikkien arvojen bittittäistä XOR-summaa (Bitwise-XOR).

Tuloste

Tulosta kokonaisluku, vastaus modulo $998,244,353$.

Esimerkki

Syöte

4
0101

Tuloste

6

Huomautus

On $6$ tapaa muodostaa puu ja vertailla lapsia: