Yana, Mino, White і Huzz — найкращі друзі.

Останнім часом Mino почувається розгубленим. Одержимий минулими невдачами в OI, він насилу планує своє майбутнє, намагаючись поєднувати це зі щільним шкільним розкладом. Троє його друзів запропонували йому оцінити важливість своїх завдань і розставити пріоритети.

Припустімо, є $n$ різних завдань, пронумерованих від $1$ до $n$. Щоразу Huzz вибирає два сусідні завдання, White порівнює їх, а Yana об'єднує їх в одне завдання. На свій подив, Mino виявляє, що цей процес випадково утворює дерево відрізків, яке не обов'язково ділиться посередині. Точніше кажучи, утворюється дерево з $2n - 1$ вершин, де кожне піддерево відповідає неперервному відрізку. Зауважте, що всі $n$ завдань є листками, а решта $n - 1$ вершин мають по два сини. Ці вершини, що виникають у результаті порівнянь, визначають значення ребер до їхніх синів: $0$ для меншого та $1$ для більшого.

Mino дуже любить обчислення. Він визначає вагу кожного завдання як XOR-суму ребер уздовж шляху від завдання до кореня. Йому цікаво: якщо ваги задано, скількома способами можна побудувати такі дерева та порівняти синів?

Знову ж таки, Mino не дуже вправний в OI, тому він звернувся по допомогу до вас. Щоб спростити задачу, вам потрібно лише знайти відповідь за модулем $998,244,353$.

Вхідні дані

Перший рядок вхідних даних містить додатне ціле число $n$ ($1 \le n \le 250000$) — кількість завдань.

Другий рядок містить двійковий рядок $S$ довжини $n$, де $S_i$ позначає побітовий XOR (Bitwise-XOR) усіх значень на ребрах від завдання $i$ до кореня.

Вихідні дані

Виведіть одне ціле число — відповідь за модулем $998,244,353$.

Приклад

стандартний ввід

4
0101

стандартний вивід

6

Примітка

Існує $6$ способів побудувати дерево та порівняти синів: