Yana, Mino, White og Huzz er bestevenner.

Mino har følt seg forvirret i det siste. Besatt av sine tidligere nederlag i OI har han slitt med å planlegge fremtiden sin samtidig som han håndterer den travle timeplanen på skolen. De tre vennene hans foreslo at han skulle vurdere viktigheten av oppgavene sine og prioritere dem.

Anta at det finnes $n$ forskjellige oppgaver nummerert fra $1$ til $n$. Hver gang velger Huzz to tilstøtende oppgaver, White sammenligner dem, og Yana slår dem sammen til én enkelt oppgave. Mino blir overrasket over å finne ut at denne prosessen tilfeldigvis danner et segmenttre, som ikke nødvendigvis deler seg på midten. Mer presist danner den et tre med $2n - 1$ noder, der hvert undertre tilsvarer et sammenhengende segment. Merk at alle de $n$ oppgavene er løvnoder, mens de andre $n - 1$ nodene har to barn hver. Disse nodene, som oppstår fra sammenligninger, definerer verdiene på kantene til barna sine: $0$ for det minste og $1$ for det største.

Mino er svært glad i utregninger. Han definerer vekten til hver oppgave som XOR-summen av kantene langs stien fra oppgaven til roten. Han lurer på: hvis vektene er gitt, hvor mange måter finnes det å konstruere slike trær og sammenligne barna på?

Igjen er ikke Mino spesielt dyktig i OI, og derfor har han henvendt seg til deg for hjelp. For å forenkle problemet trenger du bare å finne svaret modulo $998,244,353$.

Inndata

Den første linjen i inndataene inneholder et positivt heltall $n$ ($1 \le n \le 250000$), antallet oppgaver.

Den andre linjen inneholder en binær streng $S$ med lengde $n$, der $S_i$ representerer bitvis XOR (Bitwise-XOR) av alle verdiene på kantene fra oppgave $i$ til roten.

Utdata

Skriv ut et heltall, svaret modulo $998,244,353$.

Eksempel

Inndata

4
0101

Utdata

6

Forklaring

Det finnes $6$ måter å konstruere treet og sammenligne barna på: