Кевин исследует задачи, связанные с бинарными строками в Чайнатауне. Когда он был в замешательстве, к нему подошел незнакомец и предложил странную операцию:
- Пусть текущая бинарная строка — это \( t \), длина которой равна \( \vert t \vert \). Выберите целое число \( 1 \leq p \leq \vert t \vert \). Для всех \( 1 \leq i < p \) одновременно выполните операцию \( t_i = \max(t_i, t_{i+1}) \), а затем удалите \( t_p \).
Например, пусть текущая бинарная строка — это 01001, и вы выбрали \( p = 4 \). Выполните \( t_i = \max(t_i, t_{i+1}) \) для \(t_1\), \(t_2\) и \( t_3 \), преобразовав строку в 11001, затем удалите \( t_4 \), в результате получится 1101.
Кевин находит эту странную операцию довольно интересной. Таким образом, он хочет спросить вас: начиная с бинарной строки \( s \), сколько различных непустых бинарных строк вы можете получить за произвольное количество операций (возможно, ноль)?
Поскольку ответ может быть очень большим, вам нужно вывести результат по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число в отдельной строке — количество различных непустых бинарных строк, которые вы можете получить, по модулю \(998\,244\,353\).
Примечание
В первом наборе все бинарные строки, которые вы можете получить, следующие: 11001, 1001, 1101, 001, 101, 111, 01, 11 и 1. Всего \( 9 \) строк.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
11001
000110111001100
|
9
73
|