Yana, Mino, White et Huzz sont meilleurs amis.

Mino se sent confus ces derniers temps. Obsédé par ses échecs passés en OI, il a du mal à planifier son avenir tout en gérant son emploi du temps scolaire chargé. Ses trois amis lui ont suggéré d'évaluer l'importance de ses tâches et de les hiérarchiser.

Supposons qu'il y ait $n$ tâches différentes numérotées de $1$ à $n$. À chaque étape, Huzz sélectionne deux tâches adjacentes, White les compare et Yana les fusionne en une seule tâche. Mino est surpris de constater que ce processus forme accidentellement un arbre de segments, qui ne se divise pas nécessairement au milieu. Plus précisément, il forme un arbre à $2n - 1$ nœuds, où chaque sous-arbre correspond à un segment contigu. Notez que les $n$ tâches sont toutes des feuilles, tandis que les $n - 1$ autres nœuds ont chacun deux enfants. Ces nœuds, qui résultent des comparaisons, définissent les valeurs des arêtes vers leurs enfants : $0$ pour le plus petit et $1$ pour le plus grand.

Mino aime beaucoup calculer. Il définit le poids de chaque tâche comme la somme XOR des arêtes le long du chemin allant de la tâche à la racine. Il se demande : si les poids sont donnés, combien y a-t-il de façons de construire de tels arbres et de comparer les enfants ?

Une fois de plus, Mino n'est pas doué en OI, c'est pourquoi il s'est tourné vers vous pour obtenir de l'aide. Pour simplifier le problème, vous devez seulement trouver la réponse modulo $998,244,353$.

Entrée

La première ligne de l'entrée contient un entier strictement positif $n$ ($1 \le n \le 250000$), le nombre de tâches.

La deuxième ligne contient une chaîne binaire $S$ de longueur $n$, où $S_i$ représente le XOR bit à bit (Bitwise-XOR) de toutes les valeurs sur les arêtes allant de la tâche $i$ à la racine.

Sortie

Affichez un entier, la réponse modulo $998,244,353$.

Exemple

Entrée

4
0101

Sortie

6

Note

Il y a $6$ façons de construire l'arbre et de comparer les enfants :