Yana, Mino, White og Huzz eru bestu vinir.

Mino hefur verið ringlaður undanfarið. Þráhyggjufullur vegna fyrri mistaka í OI hefur hann átt í erfiðleikum með að skipuleggja framtíð sína samhliða annasalli í skólanum. Þrír vinir hans lögðu til að hann myndi meta mikilvægi verkefna sinna og forgangsraða þeim.

Gerum ráð fyrir að það séu $n$ ólík verkefni númeruð frá $1$ til $n$. Í hvert skipti velur Huzz tvö aðliggjandi verkefni, White ber þau saman og Yana sameinar þau í eitt verkefni. Mino er hissa á að uppgötva að þetta ferli myndar óvart bilatré (segment tree), sem skiptist ekki endilega í miðjunni. Nánar tiltekið myndar það tré með $2n - 1$ hnútum, þar sem hvert undirtré samsvarar samfelldu bili. Athugið að öll $n$ verkefnin eru lauf, en hinir $n - 1$ hnútarnir eiga hver um sig tvö börn. Þessir hnútar, sem verða til við samanburð, skilgreina gildi leggjanna til barna sinna: $0$ fyrir það minna og $1$ fyrir það stærra.

Mino hefur mjög gaman af útreikningum. Hann skilgreinir vigt hvers verkefnis sem XOR-summu leggjanna á veginum frá verkefninu að rótinni. Hann veltir fyrir sér: ef vigtirnar eru gefnar, á hversu marga vegu er hægt að smíða slík tré og bera saman börnin?

Enn og aftur er Mino ekki fær í OI, og þess vegna hefur hann leitað til þín eftir hjálp. Til að einfalda verkefnið þarftu aðeins að finna svarið módulo $998,244,353$.

Inntak

Fyrsta lína inntaksins inniheldur jákvæða heiltölu $n$ ($1 \le n \le 250000$), fjölda verkefna.

Önnur línan inniheldur tvíundastreng $S$ af lengd $n$, þar sem $S_i$ táknar bitbundið XOR (Bitwise-XOR) allra gilda á leggjunum frá verkefni $i$ að rótinni.

Úttak

Prentaðu heiltölu, svarið módulo $998,244,353$.

Dæmi

Inntak

4
0101

Úttak

6

Athugasemd

Það eru $6$ leiðir til að smíða tréð og bera saman börnin: