CF2201E ABBA Counting

You are given a string $ T $ of length $ n $ ( $ n $ is even), which consists of 'a', 'b', and '?'. Please count the strings $ S $ which satisfy the following conditions: - $ |S|=n $ ; - $ S_i $ is either 'a' or 'b' for all $ 1 \le i \le n $ ; - $ S_i=T_i $ for all $ 1 \le i \le n $ such that $ T_i $ is not '?'; - There exist two (possibly empty) strings $ A $ and $ B $ such that $ S=A+B+B+A $ . Here, $ + $ denotes [string concatenation](https://en.wikipedia.org/wiki/Concatenation). As the answer may be inexplicably huge, you are only asked to compute it modulo $ 998\,244\,353 $ .

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 a single integer $ n $ ( $ 2 \le n \le 400\,000 $ , $ n $ is even). The second line of each test case contains a string $ T $ of length $ n $ , consisting of 'a', 'b', and '?'. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 400\,000 $ .

For each test case, output the answer modulo $ 998\,244\,353 $ on a separate line.

For the fifth test case, there are $ 10 $ corresponding strings which are as follows: 1. "aaaabaaaaaba" 2. "aaaabbaaabba" 3. "aaabbaaaabba" 4. "aaabbbaabbba" 5. "abaabbbaabba" 6. "ababbbbabbba" 7. "baaabaaababa" 8. "baaababaaaba" 9. "baaabbaabbba" 10. "baabbabaabba"