#216865. [GKS 2022 #C] Palindromic Deletions

Games with words and strings are very popular lately. Now Edsger tries to create a similar new game of his own. Here is what he came up with so far.

Edsger's new game is called Palindromic Deletions. As a player of this game, you are given a string of length . Then you will perform the following process times:

1. Pick an index in the current string uniformly at random.
2. Delete the character at that index. You will then end up with a new string with one fewer character.
3. If the new string is a palindrome, you eat a piece of candy in celebration.

Now Edsger wonders: given a starting string, what is the expected number of candies you will eat during the game?

The first line of the input gives the number of test cases, . test cases follow. Each test case consists of two lines.

The first line of each test case contains an integer , representing the length of the string.

The second line of each test case contains a string of length , consisting of lowercase English characters.

For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the expected number of candies you will eat during the game.

should be computed modulo the prime () as follows. Represent the answer of a test case as an irreducible fraction . The number then must satisfy the modular equation , and be between and , inclusive. It can be shown that under the constraints of this problem, such a number always exists and can be uniquely determined.

样例输入 1

2
2
ab
3
aba

样例输出 1

Case #1: 2
Case #2: 333333338

In the first test case the game can go in one of ways (the character removed at each step is underlined):

1. "" "" "" (where "" denotes empty string). Both and "" are palindromes, so you will eat candies.
2. "" "" "". Both and "" are palindromes, so you will eat candies.

Overall, the expected number of candies you will eat is candies.

In the second test case, the game can go in one of ways (the character removed at each step is underlined):

1. "" "" "" ""
2. "" "" "" ""
3. "" "" "" ""
4. "" "" "" ""
5. "" "" "" ""
6. "" "" "" ""

Overall, the expected number of candies you will eat is candies.

is a uniquely determined number that satisfies the conditions mentioned in the output section as , therefore is the answer to this test.

Limits

.

String consists of only lowercase letters of the English alphabet.

Test Set

.

Test Set

.