Yana, Mino, White i Huzz są najlepszymi przyjaciółmi.

Mino czuje się ostatnio zagubiony. Prześladowany myślami o swoich dawnych porażkach w OI, z trudem planuje przyszłość, próbując jednocześnie pogodzić to z napiętym planem zajęć w szkole. Trójka jego przyjaciół zasugerowała mu, aby ocenił ważność swoich zadań i nadał im priorytety.

Załóżmy, że mamy $n$ różnych zadań ponumerowanych od $1$ do $n$. Za każdym razem Huzz wybiera dwa sąsiednie zadania, White je porównuje, a Yana scala je w jedno zadanie. Mino ze zdziwieniem odkrywa, że proces ten przypadkowo tworzy drzewo przedziałowe, które niekoniecznie dzieli przedział dokładnie na pół. Dokładniej mówiąc, powstaje drzewo o $2n - 1$ wierzchołkach, w którym każde poddrzewo odpowiada spójnemu przedziałowi. Zauważ, że wszystkie $n$ zadań jest liśćmi, natomiast pozostałe $n - 1$ wierzchołków ma po dwoje dzieci. Wierzchołki te, powstające w wyniku porównań, określają wartości krawędzi prowadzących do ich dzieci: $0$ dla mniejszego i $1$ dla większego.

Mino bardzo lubi obliczenia. Definiuje wagę każdego zadania jako sumę XOR krawędzi na ścieżce od tego zadania do korzenia. Zastanawia się: jeśli wagi są dane, na ile sposobów można skonstruować takie drzewa i porównać dzieci?

Ponownie, Mino nie jest biegły w OI, dlatego zwrócił się o pomoc do ciebie. Aby uprościć zadanie, wystarczy wyznaczyć odpowiedź modulo $998,244,353$.

Wejście

Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą $n$ ($1 \le n \le 250000$) — liczbę zadań.

Drugi wiersz zawiera napis binarny $S$ o długości $n$, gdzie $S_i$ oznacza bitowy XOR (Bitwise-XOR) wszystkich wartości na krawędziach od zadania $i$ do korzenia.

Wyjście

Wypisz jedną liczbę całkowitą — odpowiedź modulo $998,244,353$.

Przykład

Wejście

4
0101

Wyjście

6

Uwaga

Istnieje $6$ sposobów skonstruowania drzewa i porównania dzieci: