CF2255B A Ribbon for Tomorrow

Nephren has never been fond of long farewells. Before Chtholly leaves for her next mission, she says nothing and begins preparing a small ribbon for her instead. She places $ n $ glass beads in a row on the table before threading them onto the ribbon. Each bead is either white or black. A binary $ ^{\text{∗}} $ string $ s $ represents their colors: the character $ \mathtt{0} $ represents a white bead, and the character $ \mathtt{1} $ represents a black bead. To make the arrangement less ordinary, Nephren turns it into a small game. She can perform the following operation any number of times (possibly zero): - Choose two indices $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) such that $ s_l=s_r $ in the current string, and reverse $ ^{\text{†}} $ the substring $ s_l s_{l+1}\ldots s_r $ . For example, if $ s=\mathtt{00110} $ , Nephren may choose $ l=1 $ and $ r=5 $ , since $ s_1=s_5=\mathtt{0} $ . After the operation, the string becomes $ \mathtt{01100} $ . Determine the number of different binary strings that can be obtained from $ s $ . Since this number may be large, output it modulo $ 998\,244\,353 $ . $ ^{\text{∗}} $ A binary string is a string where each character is either $ \mathtt 0 $ or $ \mathtt 1 $ . $ ^{\text{†}} $ To reverse a substring $ s_l s_{l+1}\ldots s_r $ means to replace it with $ s_r s_{r-1}\ldots s_l $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of beads. The second line contains a binary string $ s $ of length $ n $ , describing the colors of the beads. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output a single integer — the number of different binary strings that can be obtained from $ s $ , modulo $ 998\,244\,353 $ .

In the first test case, exactly the following two strings can be obtained: - $ \mathtt{00110} $ ; - $ \mathtt{01100} $ . For example, reversing the entire string $ \mathtt{00110} $ produces $ \mathtt{01100} $ . In the second test case, exactly the following three strings can be obtained: - $ \mathtt{001010} $ ; - $ \mathtt{010010} $ ; - $ \mathtt{010100} $ . For example, $ \mathtt{010010} $ can be obtained by reversing the first four characters of $ \mathtt{001010} $ , and $ \mathtt{010100} $ can be obtained by reversing the entire string $ \mathtt{001010} $ . In the third test case, every substring whose endpoints contain the same character is a palindrome. Therefore, reversing any valid substring does not change the string, and only $ \mathtt{01010} $ can be obtained. In the fourth test case, we can only get $ \mathtt{111111} $ .