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$ способов построить дерево и сравнить сыновей: