P16880 [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 $N$. Then you will perform the following process $N$ 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, $T$. $T$ test cases follow. Each test case consists of two lines. The first line of each test case contains an integer $N$, representing the length of the string. The second line of each test case contains a string $S$ of length $N$, consisting of lowercase English characters.

For each test case, output one line containing Case #$x$: $E$, where $x$ is the test case number (starting from $1$) and $E$ is the expected number of candies you will eat during the game. $E$ should be computed modulo the prime $10^9 + 7$ ($1000000007$) as follows. Represent the answer of a test case as an irreducible fraction $\frac{p}{q}$. The number $E$ then must satisfy the modular equation $E \times q \equiv p \pmod{(10^9 + 7)}$, and be between $0$ and $10^9 + 6$, inclusive. It can be shown that under the constraints of this problem, such a number $E$ always exists and can be uniquely determined.

In the first test case the game can go in one of $2$ ways (the character removed at each step is underlined): 1. "$a\underline{b}$" $\to$ "$a$" $\to$ "" (where "" denotes empty string). Both $a$ and "" are palindromes, so you will eat $2$ candies. 2. "$\underline{a}b$" $\to$ "$b$" $\to$ "". Both $b$ and "" are palindromes, so you will eat $2$ candies. Overall, the expected number of candies you will eat is $\frac{2+2}{2} = 2$ candies. In the second test case, the game can go in one of $6$ ways (the character removed at each step is underlined): 1. "$\underline{a}ba$" $\to$ "$\underline{b}a$" $\to$ "$\underline{a}$" $\to$ "" 2. "$\underline{a}ba$" $\to$ "$b\underline{a}$" $\to$ "$\underline{b}$" $\to$ "" 3. "$a\underline{b}a$" $\to$ "$\underline{a}a$" $\to$ "$\underline{a}$" $\to$ "" 4. "$a\underline{b}a$" $\to$ "$a\underline{a}$" $\to$ "$\underline{a}$" $\to$ "" 5. "$ab\underline{a}$" $\to$ "$\underline{a}b$" $\to$ "$\underline{b}$" $\to$ "" 6. "$ab\underline{a}$" $\to$ "$a\underline{b}$" $\to$ "$\underline{a}$" $\to$ "" Overall, the expected number of candies you will eat is $\frac{2+2+3+3+2+2}{6} = \frac{14}{6} = \frac{7}{3}$ candies. $333333338$ is a uniquely determined number that satisfies the conditions mentioned in the output section as $333333338 \times 3 \equiv 7 \pmod{(10^9 + 7)}$, therefore $333333338$ is the answer to this test. ### Limits $1 \le T \le 20$. String $S$ consists of only lowercase letters of the English alphabet. **Test Set $1$** $2 \le N \le 8$. **Test Set $2$** $2 \le N \le 400$.