Дана бинарная строка $$$s$$$ длины $$$n$$$. Символы строки нумеруются от $$$1$$$ до $$$n$$$.

Необходимо разбить все числа от $$$1$$$ до $$$n$$$ на непустые множества так, чтобы каждое число принадлежало ровно одному множеству. Для каждой пары различных чисел $$$x$$$ и $$$y$$$ из одного множества должно выполняться хотя бы одно из условий:

• $$$s_x = s_y$$$;
• $$$|x-y| = 1$$$.

Для множества $$$M$$$ обозначим через $$$f(M)$$$ количество различных символов среди $$$s_x$$$ по всем $$$x \in M$$$. Стоимость множества $$$M$$$ равна $$$|M| \cdot f(M)$$$, где $$$|M|$$$ — количество элементов в $$$M$$$. Стоимость разбиения равна суммарной стоимости всех множеств.

Например, если дана строка $$$s$$$, равная 10001000, и мы рассматриваем разбиение на множества $$$\{1, 2\}, \{3, 8\}, \{4, 5, 6\}, \{7\}$$$, то оно корректно, и стоимость разбиения равна $$$2 \cdot 2 + 2 \cdot 1 + 3 \cdot 2 + 1 \cdot 1 = 13$$$.

Найдите максимальную стоимость разбиения и количество разбиений с такой стоимостью. Разбиения, отличающиеся только порядком множеств или порядком элементов внутри множеств, считаются одинаковыми. Количество разбиений выведите по модулю $$$998\,244\,353$$$.