26419번 - 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×q≡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.

제한

• 1ドル≤T≤20$.
• String $S$ consists of only lowercase letters of the English alphabet.

Test Set 1 (14점)

• 2ドル≤N≤8$.

Test Set 2 (27점)

• 2ドル≤N≤400$.

힌트