OpenKattis
Kattis Set 12 - Mix and Match

Start

2021-04-05 05:00 AKDT

Kattis Set 12 - Mix and Match

End

2021-04-12 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -290 days 18:22:43

Time elapsed

164:30:00

Time remaining

0:00:00

Problem D
Making Palindromes

An alphabetical string is a string consisting of $0$ or more capital letters (i.e. [‘A’..‘Z’]). Given an alphabetical string $S[1..N]$, determine the number of palindromic alphabetical strings of length $2N$ that contains $S$ as a subsequence (not necessarily contiguous). A string is palindromic if it is equal to its reverse.

Input

The first line of input is an integer representing $N$, constrained to $0 \leq N \leq 200$.

The second line of input is an alphabetical string $S$ of length $N$.

Output

Output the number of palindromic alphabetical strings of length $2N$ containing $S$ as a subsequence. As this could be rather large, output it modulo $10^9+7$.

Sample Input 1 Sample Output 1
2
AA
51
Sample Input 2 Sample Output 2
2
AB
2