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.

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 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 |