Дана двоичная строка \(s\). Двоичная строка — это строка, состоящая из символов 0 и/или 1.
Вы можете производить следующую операцию со строкой \(s\) любое количество раз (даже ноль):
- выбрать целое число \(i\) такое, что \(1 \le i \le |s|\), затем удалить символ \(s_i\).
Вам нужно сделать строку \(s\) чередующейся, т. е. после выполнения операций каждые два соседних символа в \(s\) должны быть разными.
Ваша задача — вычислить два значения:
- минимальное количество операций, необходимых для того, чтобы сделать строку \(s\) чередующейся;
- количество различных кратчайших последовательностей операций, которые делают строку \(s\) чередующейся. Две последовательности операций считаются различными, если хотя бы в одной операции выбранное целое число \(i\) отличается в этих двух последовательностях.
Выходные данные
Для каждого набора входных данных выведите два целых числа: минимальное количество операций, которые вам нужно выполнить, и количество различных кратчайших последовательностей операций. Поскольку второе число может быть большим, выведите его остаток по модулю \(998244353\).
Примечание
В первом наборе входных данных примера кратчайшими последовательностями операций являются:
- \([2]\) (удалить \(2\)-й символ);
- \([3]\) (удалить \(3\)-й символ).
Во втором наборе входных данных примера кратчайшими последовательностями операций являются:
- \([2, 1]\) (удалить \(2\)-й символ, затем удалить \(1\)-й символ);
- \([2, 2]\);
- \([1, 1]\);
- \([1, 2]\);
- \([3, 1]\);
- \([3, 2]\).
В третьем наборе входных данных примера единственной кратчайшей последовательностью операций является \([]\) (пустая последовательность).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10010
111
0101
|
1 2
2 6
0 1
|