Yana, Mino, White och Huzz är bästa vänner.

Mino har känt sig förvirrad på sistone. Besatt av sina tidigare misslyckanden i OI har han kämpat med att planera sin framtid samtidigt som han hanterar sitt fullspäckade skolschema. Hans tre vänner föreslog att han skulle utvärdera hur viktiga hans uppgifter är och prioritera dem.

Antag att det finns $n$ olika uppgifter numrerade från $1$ till $n$. Varje gång väljer Huzz två intilliggande uppgifter, White jämför dem och Yana slår ihop dem till en enda uppgift. Mino blir förvånad när han upptäcker att denna process av en slump bildar ett segmentträd, som inte nödvändigtvis delar sig på mitten. Mer precist bildar den ett träd med $2n - 1$ noder, där varje delträd motsvarar ett sammanhängande segment. Observera att alla $n$ uppgifter är löv, medan de övriga $n - 1$ noderna har två barn vardera. Dessa noder, som uppstår genom jämförelser, definierar värdena på kanterna till sina barn: $0$ för det mindre och $1$ för det större.

Mino är mycket förtjust i beräkningar. Han definierar vikten av varje uppgift som XOR-summan av kanterna längs vägen från uppgiften till roten. Han undrar: om vikterna är givna, på hur många sätt kan man konstruera sådana träd och jämföra barnen?

Återigen är Mino inte särskilt skicklig i OI, vilket är anledningen till att han har vänt sig till dig för hjälp. För att förenkla problemet behöver du bara hitta svaret modulo $998,244,353$.

Indata

Den första raden i indatan innehåller ett positivt heltal $n$ ($1 \le n \le 250000$), antalet uppgifter.

Den andra raden innehåller en binär sträng $S$ av längd $n$, där $S_i$ representerar bitvis XOR (Bitwise-XOR) av alla värden på kanterna från uppgift $i$ till roten.

Utdata

Skriv ut ett heltal, svaret modulo $998,244,353$.

Exempel

Indata

4
0101

Utdata

6

Förklaring

Det finns $6$ sätt att konstruera trädet och jämföra barnen: