[Solution] Palindromic Deletions Solution Round C 2022 - Kick Start 2022

[Solution] Palindromic Deletions Solution Round C 2022 - Kick Start 2022

Problem

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$N$. Then you will perform the following process N$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.

Solution Click Below:-  CLICK HERE

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

Input

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

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

New Password Solution Round C 2022

Range Partition Solution Round C 2022

Ants on a Stick Solution Round C 2022

Palindromic Deletions Solution Round C 2022

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

Output

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

E$E$ should be computed modulo the prime 109+7${10}^9+7$ (1000000007$1000000007$) as follows. Represent the answer of a test case as an irreducible fraction pq$\frac{p}{q}$. The number E$E$ then must satisfy the modular equation E×q≡p(mod(109+7))$E\times q\equiv p(\mathrm{mod}({10}^9+7))$, and be between 0$0$ and 109+6${10}^9+6$, inclusive. It can be shown that under the constraints of this problem, such a number E$E$ always exists and can be uniquely determined.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤20$1\le \mathbf{T}\le 20$.
String S$S$ consists of only lowercase letters of the English alphabet.

Test Set 1

2≤N≤8$2\le \mathbf{N}\le 8$.

Test Set 2

2≤N≤400$2\le \mathbf{N}\le 400$.