Yana, Mino, White und Huzz sind beste Freunde.
Mino fühlt sich in letzter Zeit verwirrt. Besessen von seinen früheren Misserfolgen bei der OI fällt es ihm schwer, seine Zukunft zu planen und gleichzeitig seinen vollen Stundenplan in der Schule zu bewältigen. Seine drei Freunde schlugen ihm vor, die Wichtigkeit seiner Aufgaben zu bewerten und sie zu priorisieren.
Nehmen wir an, es gibt $n$ verschiedene Aufgaben, die von $1$ bis $n$ nummeriert sind. Jedes Mal wählt Huzz zwei benachbarte Aufgaben aus, White vergleicht sie und Yana verschmilzt sie zu einer einzigen Aufgabe. Mino stellt überrascht fest, dass dieser Prozess zufällig einen Segmentbaum bildet, der sich nicht unbedingt in der Mitte teilt. Genauer gesagt entsteht ein Baum mit $2n - 1$ Knoten, bei dem jeder Teilbaum einem zusammenhängenden Segment entspricht. Beachte, dass alle $n$ Aufgaben Blätter sind, während die anderen $n - 1$ Knoten jeweils zwei Kinder haben. Diese aus den Vergleichen hervorgehenden Knoten definieren die Werte der Kanten zu ihren Kindern: $0$ für das kleinere und $1$ für das größere.
Mino rechnet sehr gerne. Er definiert das Gewicht jeder Aufgabe als die XOR-Summe der Kanten entlang des Pfades von der Aufgabe bis zur Wurzel. Er fragt sich: Wenn die Gewichte gegeben sind, wie viele Möglichkeiten gibt es dann, solche Bäume zu konstruieren und die Kinder zu vergleichen?
Wieder einmal ist Mino nicht besonders geschickt in der OI, weshalb er sich an dich um Hilfe gewandt hat. Um das Problem zu vereinfachen, musst du nur die Antwort modulo $998,244,353$ finden.
Eingabe
Die erste Zeile der Eingabe enthält eine positive ganze Zahl $n$ ($1 \le n \le 250000$), die Anzahl der Aufgaben.
Die zweite Zeile enthält eine Binärzeichenkette $S$ der Länge $n$, wobei $S_i$ das bitweise XOR (Bitwise-XOR) aller Werte auf den Kanten von Aufgabe $i$ zur Wurzel darstellt.
Ausgabe
Gib eine ganze Zahl aus, die Antwort modulo $998,244,353$.
Beispiel
Eingabe
4 0101
Ausgabe
6
Hinweis
Es gibt $6$ Möglichkeiten, den Baum zu konstruieren und die Kinder zu vergleichen:
