Make it Alternating
Contest: Educational Codeforces Round 155 (Rated for Div. 2)
Difficulty rating: 1300
Tags: combinatorics, dp, greedy

You are given a binary string $$$s$$$. A binary string is a string consisting of characters 0 and/or 1.

You can perform the following operation on $$$s$$$ any number of times (even zero):

- choose an integer $$$i$$$ such that $$$1 \le i \le |s|$$$, then erase the character $$$s_i$$$.

You have to make $$$s$$$ alternating, i. e. after you perform the operations, every two adjacent characters in $$$s$$$ should be different.

Your goal is to calculate two values:

- the minimum number of operations required to make $$$s$$$ alternating;
- the number of different shortest sequences of operations that make $$$s$$$ alternating. Two sequences of operations are different if in at least one operation, the chosen integer $$$i$$$ is different in these two sequences.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). The string $$$s$$$ consists of characters 0 and/or 1 only.

Additional constraint on the input:

- the total length of strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print two integers: the minimum number of operations you have to perform, and the number of different shortest sequences of operations. Since the second number might be large, print its remainder modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case of the example, the shortest sequences of operations are:

- $$$[2]$$$ (delete the $$$2$$$-nd character);
- $$$[3]$$$ (delete the $$$3$$$-rd character).

In the second test case of the example, the shortest sequences of operations are:

- $$$[2, 1]$$$ (delete the $$$2$$$-nd character, then delete the $$$1$$$-st character);
- $$$[2, 2]$$$;
- $$$[1, 1]$$$;
- $$$[1, 2]$$$;
- $$$[3, 1]$$$;
- $$$[3, 2]$$$.

In the third test case of the example, the only shortest sequence of operations is $$$[]$$$ (empty sequence).

Example input:
3
10010
111
0101

Example output:
1 2
2 6
0 1

Editorial:
Firstly, let's divide the string $$$s$$$ into blocks of equal characters. For example, if $$$s = 000100111$$$, then we divide it into four blocks: $$$000$$$, $$$1$$$, $$$00$$$, $$$111$$$. Let's denote the length of $$$i$$$-th block as $$$len_i$$$, and the number of blocks as $$$k$$$.
To obtain the longest alternating string we can get, we should choose exactly one character from each block and delete all other characters (we cannot leave two or more characters from the same block).
Now let's calculate the number of ways to choose characters that stay after string $$$s$$$ become alternating. In the first block of length $$$len_1$$$, there are $$$len_1$$$ ways to choose that element; in the second block, there are $$$len_2$$$ ways, and so on. So the final number of ways is equal to $$$\prod_{i=1}^{k} len_i$$$.
For example, let's consider the string $$$s = 00011$$$. This string is divided into two blocks $$$000$$$ and $$$11$$$, so the number of ways if $$$len_1 \cdot len_2 = 2 \cdot 3 = 6$$$:
1. 00011;
2. 00011;
3. 00011;
4. 00011;
5. 00011;
6. 00011.
However, we have chosen the characters that remain, but we need to choose the characters we erase and the order in which we erase them. Since choosing the characters that remain is basically the same as choosing the characters that get erased, we only have to choose the order in which the character get erased. The number of characters we erase is $$$n-k$$$, so the number of ways to order them is equal to the number of permutations of length $$$(n-k)$$$.
For example, let's consider that the string $$$s = 001100$$$ and the chosen indices to erase are 1, 4 and 5. Then there are $$$3! = 6$$$ ways to choose the order of them:
1. 1, 4, 5;
2. 1, 5, 4;
3. 4, 1, 5;
4. 4, 5, 1;
5. 5, 1, 4;
6. 5, 4, 1.
Note that after we delete a character from the string, the indices of other characters might change, but it doesn't actually matter.
So, the final answer is:
• the number of operations we perform is $$$n - k$$$;
• and the number of shortest sequences of operations is $$$\prod_{i=1}^{k} len_i \cdot (n-k)!$$$.