Yana, Mino, White e Huzz sono migliori amici.

Mino si sente confuso ultimamente. Ossessionato dai suoi passati fallimenti nelle OI, ha faticato a pianificare il suo futuro mentre gestisce i suoi fitti impegni scolastici. I suoi tre amici gli hanno suggerito di valutare l'importanza dei suoi compiti e di stabilire delle priorità.

Supponiamo che ci siano $n$ compiti diversi numerati da $1$ a $n$. Ogni volta, Huzz seleziona due compiti adiacenti, White li confronta e Yana li unisce in un unico compito. Mino è sorpreso nello scoprire che questo processo forma accidentalmente un segment tree, che non si divide necessariamente a metà. Più precisamente, forma un albero con $2n - 1$ nodi, in cui ogni sottoalbero corrisponde a un segmento contiguo. Nota che tutti gli $n$ compiti sono foglie, mentre gli altri $n - 1$ nodi hanno ciascuno due figli. Questi nodi, che risultano dai confronti, definiscono i valori degli archi verso i loro figli: $0$ per il minore e $1$ per il maggiore.

Mino è molto appassionato di calcoli. Definisce il peso di ciascun compito come la somma XOR degli archi lungo il cammino dal compito alla radice. Si chiede: se i pesi sono noti, in quanti modi è possibile costruire tali alberi e confrontare i figli?

Ancora una volta, Mino non è abile nelle OI, ed è per questo che si è rivolto a te per chiedere aiuto. Per semplificare il problema, devi solo trovare la risposta modulo $998,244,353$.

Input

La prima riga dell'input contiene un intero positivo $n$ ($1 \le n \le 250000$), il numero di compiti.

La seconda riga contiene una stringa binaria $S$ di lunghezza $n$, dove $S_i$ rappresenta lo XOR bit a bit (Bitwise-XOR) di tutti i valori sugli archi dal compito $i$ alla radice.

Output

Stampa un intero, la risposta modulo $998,244,353$.

Esempio

Input

4
0101

Output

6

Note

Ci sono $6$ modi per costruire l'albero e confrontare i figli: